Please use this identifier to cite or link to this item: https://hdl.handle.net/11147/11710
Title: Tracking and prediction of evolution of communities in dynamic networks
Other Titles: Dinamik ağlarda toplulukların gelişiminin izlenmesi ve kestirimi
Authors: Şahin, Serpil
Karataş, Arzum
Izmir Institute of Technology
Keywords: Community evolution
Community tracking
Locality sensitive hashing
Dynamic network analysis
TREC method
Social networks
Issue Date: Jul-2021
Publisher: Izmir Institute of Technology
Source: Karataş, A. (2021). Tracking and prediction of evolution of communities in dynamic networks. Unpublished doctoral dissertation, Izmir Institute of Technology, Izmir, Turkey
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.
Description: Thesis (Doctoral)--Izmir Institute of Technology, Computer Engineering, Izmir, 2021
Includes bibliographical references (leaves. 90-100)
Text in English; Abstract: Turkish and English
URI: https://hdl.handle.net/11147/11710
Appears in Collections:Phd Degree / Doktora

Files in This Item:
File Description SizeFormat 
10149912.pdf
  Until 2022-03-13
Doctoral Thesis3.3 MBAdobe PDFView/Open    Request a copy
Show full item record

CORE Recommender

Page view(s)

38
checked on Nov 29, 2021

Google ScholarTM

Check


Items in GCRIS Repository are protected by copyright, with all rights reserved, unless otherwise indicated.