Geri Dön

Novel centrality, topology and hierarchical-aware link prediction in dynamic networks

Dinamik ağlarda merkezilik, topoloji ve hiyerarşik tabanlı bağlanti tahmini

PDF İndir

  1. Tez No: 901275
  2. Yazar: ABUBAKHARI SSERWADDA
  3. Danışmanlar: DOÇ. DR. YUSUF YASLAN, YRD. DOÇ. ALPER ÖZCAN
  4. Tez Türü: Doktora
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2023
  8. Dil: İngilizce
  9. Üniversite: İstanbul Teknik Üniversitesi
  10. Enstitü: Lisansüstü Eğitim Enstitüsü
  11. Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Bilgisayar Mühendisliği Bilim Dalı
  13. Sayfa Sayısı: 120

Özet

Sosyal ağ verilerinin artan kullanılabilirliği, sosyal ağ ile ilgili uygulamalara çözüm bulmayı amaçlayan araştırmaların ortaya çıkmasına neden olmuştur. Bununla birlikte, sosyal ağ elemanları arasındaki etkileşimlerin genişliği ve karmaşıklığı, elemanlar arasındaki ilişkilerin tahminini zorlu bir görev haline getirir. Önceki çalışmalar genellikle ağı tanımlayıcı diğer önemli özellikleri ihmal ederek yalnızca yerel düğüm bağlantı bilgilerini keşfetmeye odaklanmaktadır. Genellikle hafife alınan temel ağ karakterize edici özellikler arasında ağ topolojisi, düğüm yapısal merkezilik rolleri ve ağ hiyerarşik bilgileri bulunur. Ek olarak, çoğu çalışma; ağı statik olarak kabul eder, ancak bir çok gerçek dünya verisi zaman içinde değişmektedir. Bu çalışmada bu sınırlamaların üstesinden gelmek için, öncelikle Common Neighbour, Jaccard Index, Adamic Adder, Salton Index, Resource Allocation, and Sørensen Index gibi başarılı topolojik benzerlik ölçümlerini kullanarak çeşitli topolojik benzerlik tabanlı evrişim özellik matrisi hesaplanmaktadır. Ardından, girdi grafiklerinden temel topolojik bilgileri verimli bir şekilde yakalamak için ortaya çıkan topolojik özellik matrislerini kullanırız. İkinci olarak, ağ boyunca düğüm merkezilik rollerini ve düğümün yapısal bağlantı bilgisini korumak için düğüm derecesinin daha güçlü bir varyantı olan düğüm gücü merkeziyet matrisinden yararlanırız. Ek olarak, nitelikli üst düzey özellik gömmeleri elde etmek için bu tür çeşitli özellikleri sistematik olarak bir araya getiriyoruz. Son olarak, örtük ağ geçici bilgilerini keşfetmek için bir LSTM katmanı kullanıyoruz. Düşük boyutlu düğüm gömmelerini öğrenmek için, önce, yüksek kaliteli düğüm gömmelerine giriş grafiklerindeki varyasyonları etkili bir şekilde tespit eden tam bağlantılı bir varyasyonel otomatik kodlayıcı kullandık. Ayrıca, öğrenilen gömmelerde giriş grafiklerinin topolojik yapısının ve merkeziliğinin korunmasını daha da güçlendirmek için model öğrenimine topolojik benzerlik ve merkezilik kısıtlamalarını uyguladık. Ek olarak, nitelikli üst düzey özellik gömmeleri elde etmek için bu tür çeşitli özellikleri sistematik olarak bir araya getiriyoruz. Son olarak, örtük ağ geçici bilgilerini keşfetmek için bir LSTM katmanı kullanıyoruz. Düşük boyutlu düğüm gömmelerini öğrenmek için, önce, yüksek kaliteli düğüm gömmelerine giriş grafiklerindeki varyasyonları etkili bir şekilde tespit eden tam bağlantılı bir varyasyonel otomatik kodlayıcı kullandık. Ayrıca, öğrenilen gömmelerde giriş grafiklerinin topolojik yapısının ve merkeziliğinin korunmasını daha da güçlendirmek için model öğrenimine topolojik benzerlik ve merkezilik kısıtlamalarını uyguladık. Bununla birlikte, varyasyonel otomatik kodlayıcılar, özellikle büyük ağlarda doğrusal kodlayıcı ve kod çözücüleri tanımlayan çok sayıda parametre nedeniyle büyük hesaplama süresi ve bellek gereksinimlerine ihtiyaç duyar. Hesaplama süresini ve bellek gereksinimlerini en aza indirirken uygulamalarımızı büyük veri kümelerine genişletmek için Grafik Evrişim Ağı (GCN) tabanlı bir uygulamayı benimsedik. Önerilen Yapısal ve Topolojik tabanlı geometrik derin öğrenme yaklaşımı, gerçek dünyadaki en fazla beş geçici sosyal ağ üzerinde test edilmiştir. Deneysel sonuçlara dayalı olarak, ortalama olarak, en iyi kıyaslamalarla karşılaştırıldığında, bağlantı tahmini doğruluğunda \%4'lük bir bağlantı tahmini AUC iyileştirmesi, her epoch için ihmal edilebilir eğitim süresi artışı ve yapısal merkezilik tahmininde \%56'lık bir MSE azalma sağlarlar. Zamansal ağ modelleri için önerilen uçtan uca topolojik benzerlik ve merkezilik farkında bağlantı tahmini, yalnızca öğrenilen yerleştirmelerdeki topolojik benzerlik ve merkezilik bilgisini korumakla kalmaz, aynı zamanda dinamik ağlarda örtük zamansal bilgiyi de keşfeder. Modeller, ağ topolojisinin korunmasını ve gömmeleri öğrenme sırasında düğümlerin yapısal merkezilik rolünü yakalamak ve uygulamak için topolojik benzerlik özelliklerini, düğüm merkezilik özelliklerini ve ilgili kısıtlamaları kullanır. Böylece, bağlantı tahmini ve merkezilik tahmini doğruluklarını artıran yüksek kaliteli yerleştirmeler elde edilir. Diğer ilgili çalışmada, Hiyerarşik ve Merkeziyet odaklı bir Polifarmasi Yan Etki Tahmin Modeli (HC-POSE) tanıtıyoruz. Yan etki tahminini bir bağlantı tahmin görevi problemi olarak modelliyoruz ve heterojen protein-protein, protein-ilaç ve ilaç-ilaç etkileşimi veri kümelerindeki temel hiyerarşik bilgileri keşfetmek için çekirdek ayrışımından yararlanıyoruz. K-çekirdek ayrışımının ardından, ortaya çıkan her k-çekirdek için, her bir alt grafiğin merkezilik bilgisini depolamak için bir düğüm gücü matrisi hesaplanır; bu matris, daha yüksek seviye özellik gömmelerine sahip olmak için k-çekirdek bitişik matris ile sistematik olarak toplanır. Homojen alt grafikler için düşük boyutlu gösterimleri öğrenmek üzere GCN tabanlı bir otomatik kodlayıcı ve heterojen alt grafikler için RCGN tabanlı bir otomatik kodlayıcı kullandık. Deneysel sonuçlara dayalı olarak, HC-POSE, POSE tahmin doğruluğunda en iyi çalışmaya göre \%3'lük bir gelişme sergiledi. Bunun nedeni, modelin bu tür heterojen ağlarda hakim olan hiyerarşik ve merkezi bilgileri verimli bir şekilde yakalama yeteneğidir. %%%%%%%%%%%%%% Veri kümelerini inceliyoruz ve veri kümelerinin yapısına uyması için daha iyi ağ özelliği ölçümleri öneriyoruz. Örneğin, yüksek hiyerarşiye sahip veri kümelerinde, gömme vektörlerini öğrenme sırasında verilerin yapısından verimli bir şekilde yararlanmak için hiyerarşik tabanlı yaklaşımlar öneriyoruz. Düğümün merkeziliğini ve yapısal rollerini korumak için, düğüm derecesi merkeziliğinin güçlü bir varyantı olan kuvvet merkeziliğini seçiyoruz çünkü yüksek derecede merkeziliğe sahip düğümler, diğer merkezilik ölçütlerinde (arada olma merkeziliği, yakınlık merkeziliği ve öz merkeziliği) yüksek puanlara sahip olma eğilimindedir. Önerilen modellerimizin pratik uygulanabilirliğini gösterdik ve modelleri gerçek dünyadaki klinik polifarmasi yan etki veri kümeleri, iletişim veri kümeleri ve sosyal ağ veri kümeleri (Facebook, e-posta mesajları ve yığın taşma veri kümeleri) üzerinde uygulayarak verimliliklerini değerlendirdik. Önerdiğimiz ağ özelliğine dayalı gömme modelleri, diğer birçok gerçek dünya problemini çözmek için genişletilebilir. Örneğin, tanıttığımız ağ topolojisi ve düğüm merkeziliği yerleştirme öğrenme modelleri, verileri istenen ağ özellikleriyle sentezlemek için grafik üreten ağlar ve çekişmeli üretken ağlar dahil olmak üzere veri artırma modelleriyle esnek bir şekilde entegre edilebilir. Bu, kaliteli ağ özelliğine duyarlı beyin bağlantılarını, ilaç-ilaç etkileşimlerini ve ilaç-hastalık etkileşimi veri kümelerini artırarak, özellikle kıt klinik veri kümeleri için veri kıtlığı sorunlarını çözebilir. Ayrıca, gömme öğrenme sırasında her bir ağ özelliğinin korunmasına verilen önemi düzenlemek için parametreler sunuyoruz. Bu, gömülü öğrenme sırasında en çok istenen ağ özelliklerine daha fazla ağırlık vererek oluşturulan verilerin yapısının özelleştirilmesine önemli ölçüde yardımcı olur. Bu tezde önerilen modellere değer katmak için uyarlanabilecek açık fırsatları ve gelecekteki çalışmaları vurguluyoruz. Öğrenilen gömmelerin kalitesini artırmak için keşfedilebilecek diğer ağ özelliklerini tartıştık. Böylece, doğruluğu öğrenilen gömmelerin kalitesine bağlı olan bağlantı tahmini, düğüm sınıflandırması ve grafik kümeleme gibi uç ağ uygulamalarının doğruluğunu iyileştirmek. Yaklaşımımız sayesinde, geometrik derin öğrenme modelleri tarafından üretilen yerleştirmelerin kalitesini artırmak amacıyla modülerlik ve yayılma katsayısı dahil olmak üzere diğer merkezilik ölçülerini, topolojik benzerlik ölçümlerini ve diğer önemli ağ karakterize edici özellikleri keşfetmek için yönler ve fırsatlar yaratıyoruz.

Özet (Çeviri)

The increasing availability of social network data has given rise to research devoted to solving problems associated with social network-related applications. However, the hugeness and complexity of relationships among social network elements render the prediction of links between the entities a challenging task. The previous research often focuses primarily on investigating local node connectivity data while ignoring other important network-characterizing properties. The key network-characterizing properties that are often underrated include network topology, node structural centrality roles, and network hierarchical information. Furthermore, whereas many real-world graphs change over time, several works assume static networks. In order to overcome these challenges, first, we compute several topological similarity-based convolution feature matrices by using various topological similarity metrics such as Common Neighbour, Jaccard Index, Adamic Adder, Salton Index, Resource Allocation, and Sørensen Index. We then utilize the resulting topological feature matrices to capture the prevailing topological information in the input graphs efficiently. Second, we leverage the strength centrality, a stronger variant of node degree, to conserve the node's centrality and the structural connectivity information in the network. In addition, we systematically aggregate such diverse features to yield quality higher-level feature representations. Lastly, we leverage an LSTM layer to capture the prevailing temporal information in the graph sequences. To learn the low dimensional node representations, first, we deployed a fully connected variational autoencoder that efficiently explores variations in the input graphs to learn high-quality node embeddings. Furthermore, we imposed centrality and topological constraints on the learning model to further enforce the preservation of the centrality and topological ınformation of input graphs in the learned embeddings. However, variational autoencoders have large computational time and memory requirements due large number of parameters characterizing the fully connected encoders and decoders, especially when they are applied on large networks. In order to extend our implementations to large datasets while minimizing the computational time and memory requirements, we adopted a Graph Convolution Network (GCN)-based implementation. The proposed Structural and Topological based geometric deep learning approach was evaluated on five real-world temporal social networks. Based on experimental results, on average, they yield a 4\% link prediction AUC improvement in link prediction accuracy, a small increment in training for each epoch (0.2s (10\%)), and a 56\% MSE reduction in centrality prediction when compared to the best benchmarks. The proposed end-to-end centrality and topological guided link prediction framework for dynamic networks preserve not only the centrality node roles and the topological information in the learned embeddings but also captures the prevailing temporal information in the dynamic networks. The models utilize node centrality and topological features to capture and conserve the network topology and the structural roles of nodes during embedding learning. Thus, obtaining pretty-quality embeddings that enhance the link prediction and centrality prediction accuracies. For all our proposed methods, we assess the impact of the various modules of the proposed models by comparing them with their variants that lack such modules, and we present and explain the results accordingly. In other related work, we introduce a Hierarchical and Centrality aware Polypharmacy Side Effect Prediction (HC-POSE) Model. We model side effect prediction as a link prediction task problem and leverage core decomposition to explore the prevailing hierarchical information in the heterogeneous protein-protein, protein-drug, and drug-drug interaction datasets. Following k-core decomposition, for each k-core subgraph produced, a node strength matrix is computed to store the centrality information of each subgraph. Then we systematically aggregate the obtained centrality with the k-core adjacency matrix to have higher-level diverse feature representations. We deployed a GCN-based auto-encoder to learn low-dimensional representations for the homogeneous sub-graphs and an RCGN-based auto-encoder for the heterogeneous subgraphs. Based on the experimental results, HC-POSE exhibited a 3\% accuracy improvement in POSE prediction as compared to the best baseline. This is due to the ability of the model to efficiently capture the prevailing hierarchical and centrality information in such heterogeneous networks. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% We study datasets and propose better network property metrics to suit the structure of the datasets. For instance, datasets with high hierarchies, we propose hierarchical-based approaches to efficiently benefit from the structure of the data when embedding learning. To preserve the node's centrality and structural roles, we choose strength centrality, a powerful variant of the node degree centrality, since nodes with high degree centrality tend to have high scores in other centrality metrics (betweeness centrality, closness centrality and eigen centrality). We demonstrated our proposed models' practical applicability and assessed their efficiency by implementing the models on real-world clinical polypharmacy side effect datasets, communication datasets, and social network datasets (Facebook, email messages, and stack overflow datasets). The network property-based embedding models we propose can be extended to solve many other real-world problems. For instance, the proposed network topology and node centrality aware embedding learning models can be flexibly integrated with data augmentation models, including graph-generating networks and generative adversarial networks to synthesize data with desired network properties. This could solve data scarcity problems, especially for the scarce clinical datasets, by augmenting quality network property-aware brain connectomes, drug-drug interactions, and drug-disease interaction datasets. Moreover, we introduce parameters for regulating the importance attached to the conservation of each network property during embedding learning. This significantly helps in customizing the structure of the generated data by attaching more weight to the most desired network properties during embedding learning. We highlight open opportunities and future works that can be adapted to add value to the proposed models in this dissertation. We discussed other network properties that can be explored so as to improve the quality of learned embeddings. Thus, improving the accuracy of the end network applications, such as link prediction, node classification, and graph clustering, whose accuracy depends on the quality of learned embeddings. By following our approaches, we open directions and opportunities for exploring other centrality measures, more topological similarity metrics and other key network-characterizing properties including the modularity and diffusion coefficient, so as to enhance the quality of embeddings generated by geometric deep learning models.

Benzer Tezler

  1. Tez No

    433996

    Network topology and dynamic data analysis in Saccharomyces cerevisiae

    Ağ ilingesi ve Saccharomyces cerevisiae'de devingen veri analizi

    MUHAMMED ERKAN KARABEKMEZ

    Doktora

    İngilizce

    İngilizce

    2016

    BiyomühendislikBoğaziçi Üniversitesi

    Kimya Mühendisliği Ana Bilim Dalı

    PROF. DR. BETÜL KIRDAR

  2. Tez No

    542352

    Analysis of biochemical pathway with graph based algorithms

    Biyokimyasal yolaklarda çizge teorisi algoritmalarıyla analiz

    EMİNE RAVZA GÜR

    Yüksek Lisans

    İngilizce

    İngilizce

    2018

    BiyomühendislikYıldız Teknik Üniversitesi

    Biyomühendislik Ana Bilim Dalı

    DR. ÖĞR. ÜYESİ ALPER YILMAZ

  3. Tez No

    559449

    Predicting potential allosteric communication pathways in pyruvate kinase using residue network model

    Rezidü ağ modelini kullanarak piruvat kinazdaki potansiyel allosterik iletişim yollarının tahmini

    ZEHRA SARICA

    Yüksek Lisans

    İngilizce

    İngilizce

    2019

    Kimya Mühendisliğiİstanbul Teknik Üniversitesi

    Kimya Mühendisliği Ana Bilim Dalı

    DR. ÖĞR. ÜYESİ AYŞE ÖZGE KÜRKÇÜOĞLU LEVİTAS

  4. Tez No

    485812

    International financial integration: A complex network analysis

    Uluslararası finansal entegrasyonu: Karmaşık bir ağ yaklaşımı

    ORNELA VLADI

    Yüksek Lisans

    İngilizce

    İngilizce

    2017

    EkonomiSakarya Üniversitesi

    Uluslararası Ticaret Ana Bilim Dalı

    DOÇ. DR. HAKAN TUNAHAN

  5. Tez No

    418617

    Centrality measures on networks and empirical analysis on activity driven network models

    Ağlarda merkeziyet ölçüleri ve aktiviteye dayalı ağlarda deneysel analizler

    ECE NAZ DUMAN

    Yüksek Lisans

    İngilizce

    İngilizce

    2015

    Endüstri ve Endüstri MühendisliğiSabancı Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    PROF. DR. ALİ RANA ATILGAN

Geri Dön