Algebraic methods for link predictionin very large networks
Büyük ağ verilerinde düğüm tahminleme için cebirsel metotlar
- Tez No: 738591
- Danışmanlar: PROF. DR. MEHMET KOYUTURK
- Tez Türü: Doktora
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Güçlü Yapay Zeka Kuramı, Powerful Artifical Intellegence Theory
- Yıl: 2017
- Dil: İngilizce
- Üniversite: Case Western Reserve Unıversıty
- Enstitü: Yurtdışı Enstitü
- Ana Bilim Dalı: Bilgisayar Bilimleri Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
Düğüm bağlantı tahminleme problemi bir çok ağ analitiği probleminde yer almaktadır, örneğin, bilgi çekme, tavsiye sistemeleri, sanal tehtit belirleme, protein hastalık ilişkilerini açığa çıkarma, vb. Genel anlamı ile bu problemi çözmek içim ağlarda farklı düğümlerin direk olmayan bağlantılarının çok faydalı olduğu görülmüştür. Bu direl olmayan bağlantıları bulabilmek için etkili direnç ve ransgele yürüyüş gibi algoritmalar literatürde mevcuttur. Ancak, bu algoritmaların milyonlarca düğüm içeren ağlarda çalışması çok zaman almaktadır. Bu problemi gidermek için, bu tezde, Chopper ve I-Chopper isminde iki tane algoritma geliştirilmiştir. Bu algoritmalar genel anlamı ile Chebyshev Polinomları üzerine inşa edilmiştir ve var olan algoritmalardan kat kat daha hızlı çalışmaktadır. Son olarak, ransgele yürüme algoritmasının çok bağlantılı düğümleri kayırıdığı gözlemlenmiştir. Bu kayırmayı giderebilmek için, Sparse Correlation isminde bir yöntem geliştirilmiş ve bu yöntemin daha iyi düğüm bağlantı tahminleme yaptığı gösterilmiiştir.
Özet (Çeviri)
Link prediction is at the heart of a large class of network analytics and information retrieval techniques, including recommendation systems, threat detection, and disease gene prioritization, among others. A commonly utilized feature in link prediction is network proximity, which is assessed using a variety of algorithms, ranging from effiective resistance to random walks. Network proximity is useful in link prediction since it has been repeatedly shown in many contexts that nodes that have many shared connections or are proximate to each other are likely to interact with each other in the future. Many network proximity measures are based on algebraic formulations and their computations utilize iterative methods. Owing to their importance, signifi cant e ort has been devoted to accelerating the iterative processes that underlie network proximity computations. These techniques rely on numerical properties of power iterations, as well as structural properties of the networks to reduce the runtime of iterative algorithms. However, the acceleration provided by existing techniques is usually not sufficient to enable real-time processing of proximity queries on networks with millions of nodes and tens of millions of edges. In this thesis, we present several algebraic approaches to the acceleration of network proximity queries, with a view to facilitating real-time query processing on very large networks. We fi rst develop an algorithm to speed up the iterative computation of random walk-based proximity, using Chebyshev polynomials for undirected networks. We show that our approach, called Chopper yields provable improvements in convergence rate, and signifi cantly reduced convergence times in practice. We then focus on the same problem for directed networks, and develop an indexing scheme that exploits the sparsity of real-life networks. We show that our algorithm, I-Chopper, signi cantly outperforms existing methods and it o ers both scalability and efficiency for processing network proximity queries on very large directed graphs. Specifi cally, I-Chopper drastically reduces the convergence time of the iterative procedure, while also minimizing the storage requirements for indexing. Using a number of large real-world networks, and top-k proximity queries as the benchmark problem, we show that our methods outperform existing methods for wide ranges of parameter values. Lastly, we apply these methods to link prediction and propose two proximity-based link prediction techniques that can capture network topology by utilizing network modularity and sparsity through network proximity queries. We comprehensively test the performance of the resulting algorithms and compare them against state-of-the art link prediction techniques. Our results show that the resulting algorithms drastically improve the performance of unsupervised link prediction methods.
Benzer Tezler
- İzometriler ve diferansiyel geometri
Başlık çevirisi yok
NEJAT EKMEKÇİ
Yüksek Lisans
Türkçe
1987
MatematikGazi ÜniversitesiMatematik Ana Bilim Dalı
PROF. DR. HASAN HİLMİ HACISALİHOĞLU
- Matris lie gruplarının lie cebirleri
Başlık çevirisi yok
SIRRI AYDINTAN
Yüksek Lisans
Türkçe
1986
MatematikGazi ÜniversitesiMatematik Ana Bilim Dalı
YRD. DOÇ. DR. BÜLENT KARAKAŞ
- Süpermanifoldlar üzerinde süpervektör yapıları ve süpereğriler
Başlık çevirisi yok
HASAN HÜSEYİN UĞURLU
Yüksek Lisans
Türkçe
1987
MatematikGazi ÜniversitesiMatematik Ana Bilim Dalı
YRD. DOÇ. DR. BÜLENT KARAKAŞ
- Kutu kesitli kirişlerin eğilme, burulma ve bozulma etkilerine göre analizi
Başlık çevirisi yok
AHMET BUDAK
Yüksek Lisans
Türkçe
1987
İnşaat MühendisliğiKaradeniz Teknik Üniversitesiİnşaat Mühendisliği Ana Bilim Dalı
DOÇ. DR. İLHAN SUNGUR