Login | Register

Community Detection In Evolving Networks


Community Detection In Evolving Networks

Puranik, Tejas ORCID: https://orcid.org/0000-0001-6753-7986 (2017) Community Detection In Evolving Networks. Masters thesis, Concordia University.

[thumbnail of Puranik_MCompSc_S2017.pdf]
Text (application/pdf)
Puranik_MCompSc_S2017.pdf - Accepted Version
Available under License Spectrum Terms of Access.


Most social networks are characterized by the presence of community structure, viz. the existence of clusters of nodes with a much higher proportion of links within the clusters than between the clusters. Community detection has many applications in many kinds of networks, including social networks and biological networks. Many different approaches have been proposed to solve the problem. An approach that has been shown to scale well to large networks is the Louvain method, based on maximizing modularity, which is a quality function of a partition of the nodes.

In this thesis, we address the problem of community detection in evolving social networks. As social networks evolve, the community structure of the network can change. How can the community structure be updated in an efficient way? How often should community structure be updated? In this thesis, we give two methods based on the Louvain algorithm, to determine when to update the community structure. The first method, called the Edge-Distribution-Analysis algorithm, analyzes the newly added edges in order to make this decision. The second method, called the Modularity-Change-Rate algorithm, finds the rate of modularity change in a given network, and uses it to predict whether an update is required.

Due to the sparsity of real datasets of evolving networks, we propose three models to generate evolving networks: a Random model, a model based on the well-known phenomenon of homophily in social networks, and another based on the phenomenon of triadic and cyclic closure. Starting with real-world data sets, we used these models to generate evolving networks. We evaluated the Edge-Distribution-Analysis algorithm and Modularity-Change-Rate algorithm on these data sets. Our results show that both our methods predict quite well when the community structure should be updated. They result in significant computational savings compared to approaches that would update the community structure after a fixed number of edge additions, while ensuring that the quality of the community structure is comparable.

Divisions:Concordia University > Gina Cody School of Engineering and Computer Science > Computer Science and Software Engineering
Item Type:Thesis (Masters)
Authors:Puranik, Tejas
Institution:Concordia University
Degree Name:M. Comp. Sc.
Program:Computer Science
Date:16 March 2017
Thesis Supervisor(s):Narayanan, Lata
ID Code:982242
Deposited On:09 Jun 2017 15:01
Last Modified:18 Jan 2018 17:54
All items in Spectrum are protected by copyright, with all rights reserved. The use of items is governed by Spectrum's terms of access.

Repository Staff Only: item control page

Downloads per month over past year

Research related to the current document (at the CORE website)
- Research related to the current document (at the CORE website)
Back to top Back to top