Tracking and prediction of evolution of communities in dynamic networks

Abstract

Communities are the most meaningful structures in dynamic networks. Tracking this evolution provides insights into the patterns of community evolution in networks over time and valuable information for decision support systems in many research areas such as marketing, recommender systems, and criminology. Previous work has focused on either high accuracy or time efficiency, but not on low memory consumption. This motivates us to develop a method that combines highly accurate tracking results with low computational resources. This dissertation first provides a brief overview of research in dynamic network analysis. Then, a novel space-efficient method, called TREC, for tracking the evolution of communities in dynamic networks is presented, where community matching using LSH with minhasing technique is proposed to efficiently track similar communities in terms of memory consumption over time. The accuracy of TREC is evaluated on benchmark datasets, and the execution time performance is measured on real dynamic datasets. In addition, a comparative algorithmic complexity analysis of TREC in terms of space and time is performed. Both theoretical and experimental results show that TREC outperforms competitor methods on both datasets in terms of combination of space, accuracy, and execution time. Next, it is investigated that whether the TREC method is suitable for predicting the evolution of community areas. In this evaluation, a prediction study is conducted. A common methodology is followed which includes main steps such as feature extraction, feature selection, classifier training and cross validation. Experimental results show that TREC method is suitable for predicting evolution of communities.

Topluluklar dinamik ağlarda karşılaşılan anlamlı yapılardır. Bu ağlardaki toplulukların zaman içerisindeki olası gelişimlerinin takibi farklı alanlardaki araştırma ve karar destek sistemleri için değerli bilgiler sağlar; örneğin bilimsel araştırmalarda, sosyal ağlarda ilgi alanlarındaki değişimin incelenmesi ve suç kestiriminin sağlanmasında, reklam ve pazarlama sistemlerinin yönlendirilmesinde vb. Var olan çalışmalar ya yüksek başarıma ya da zaman verimliliğine odaklanmış, bellek kullanım verimliliği incelenmemiştir. Dolayısıyla, toplulukların gelişimini düşük hesaplama kaynağı kullanarak yüksek başarımla izleyebilecek bir yöntem geliştirme bu tezin motivasyonunu oluşturur. Bu doktora tezinde, dinamik bir ağda, benzer toplulukları takip etmek ve benzerlik ilişki tipini belirlemede TREC adında özgün bir yöntem önerilmiştir. Yöntem, bellek kullanım verimliliği için LSH ve minhashing tekniği kullanılarak topluluk eşleştirmesi yapar. Önerilen TREC yönteminin sonuçlarına ait doğrulama ve çalışma zamanı gibi verimlilik analizleri gerçekleştirilmiştir. Yöntemin, benzer ve güncel olan en iyi çalışmalar ile karşılaştırılması ise; hem deneysel uygulamalar ile hem de kullanılan zaman ve bellek alanı açısından algoritmik karmaşıklık analizleri ile sağlanmıştır. Sonuçlar; TREC yönteminin bellek alanı gereksinimi, doğruluk ve çalışma zamanı tüketiminin kombinasyonu ile hem deneysel hem de gerçek veri setlerinde benzer çalışmalara göre üstünlük içerdiğini göstermiştir. Tezin ana çalışmasına ek olarak; toplulukların gelişiminin kestiriminde TREC yönteminin uygulanabilirliği de değerlendirilmiş, makine öğrenmesine dayalı kestirimci bir çalışma yürütülmüştür. Bu aşamada, yeni bir makine öğrenmesi yöntemi geliştirilmesi ya da yeni bir yöntembilim önerilmesi hedeflenmemiştir. Bu nedenle, özniteliklerin belirlenmesi, özniteliklerin seçilmesi, sınıflandırıcıların eğitilmesi ve çapraz geçerlilik ana basamaklarını içeren yaygın bir yöntembilim izlenmiştir. Buradaki sonuçlar; TREC yönteminin kestirim alanında benzer çalışmalar ile eş başarım düzeyinde olduğunu ve uygulanabilir olduğunu göstermektedir.