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: Belirtilmemiş.
- Yıl: 2017
- Dil: İngilizce
- Üniversite: Case Western Reserve University
- Enstitü: Yurtdışı Enstitü
- Ana Bilim Dalı: Bilgisayar Bilimleri Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 122
Ö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
- Trajectory tracking control of robotic manipulatörs with flexible joints
Elastik eklemli bir robot kolun konum kontrolü
İNANÇ ERDAĞI
Yüksek Lisans
İngilizce
1995
Makine MühendisliğiOrta Doğu Teknik ÜniversitesiDOÇ.DR. S. KEMAL İDER
PROF.DR. KEMAL ÖZGÖREN
- Efficientmethods for the kinematic analysis of spatial mechanisms and robots
Uzaysal mekanizma ve robotların kinematik analizi için etkin metodlar
MUHTAR BURAK AKBULUT
Yüksek Lisans
İngilizce
1994
Makine MühendisliğiOrta Doğu Teknik ÜniversitesiMakine Mühendisliği Ana Bilim Dalı
DOÇ. DR. REŞİT SOYLU
- Tek kişilik yatak koltuk mekanizması tasarımı ve kinematik analizi
Reclining chair mechanism design and kinematic analysis
AYHAN BEKKİ
Yüksek Lisans
Türkçe
2017
Makine MühendisliğiCumhuriyet ÜniversitesiMakine Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. HACI ALİ ERTAŞ
- Akarsu havzası sistemlerinin planlanması için genel maksatlı bir simülasyon modeli
A General-purpose simulation model for planning of river basın systems
DEMİRAY ŞİMŞEK