Design, Analysis and Experimental Evaluation of a Distributed Community Detection Algorithm

Complex networks are a special type of graph that frequently appears in nature and in many different fields of science and engineering. Studying complex networks is the key to solve the problems in these fields. Complex networks have unique features which we cannot find in regular graphs, and the study of complex networks gives rise to many interesting research questions. An interesting feature to study in complex networks is community structure. Intuitively speaking, communities are group of vertices in a graph that are densely connected with each other in the same group, while sparsely connected with other nodes in the graph. The notion of community has practical significance. Many different concept and phenomenons in real world problems can be translated into communities in a graph, such as politicians with similar opinions in the political opinion network. In this thesis work, a distributed version of a popular community detection method-Louvain method-is developed using graph computation framework Apache Spark GraphX. Characteristics of this algorithm, such as convergence and quality of communities produced, are studied by both theoretical reasoning and experimental evaluation. The result shows that this algorithm can parallelize community detection effectively. This thesis also explores the possibility of using graph sampling to accelerate resolution parameter selection of a resolution-limit-free community detection method. Two sampling algorithms, random node selection and forest fire sampling algorithm, are compared. This comparison leads to suggestions of choice of sampling algorithm and parameter value of the chosen sampling algorithm.

Subject

complex network
community detection
distributed computing

To reference this document use:

http://resolver.tudelft.nl/uuid:5ef1696a-0ef8-4d4c-a807-3d0fd3247b1d

Part of collection

Student theses

Document type

master thesis

Rights

Files

PDF

thesis.pdf

3.95 MB

Close viewer