Community detection in complex networks using local methods and information flow

Abstract

Many real world systems can be represented using networks or graphs where ele ments of system are denoted by nodes and their relations by edges. Complex networks are special kinds of these networks with their emergent features created by interactions among nodes. One such emergent feature is the community structure. A community is a group of nodes where nodes within same community have more connections (i.e., edges) with each other than with the nodes in the rest of the network. Identifying such communities is the task of community detection that can be used to identify nodes with similar functions or features, densely connected regions in networks, information flow patterns and spreading of a disease or information in a network. In this thesis, we work on community detection on complex networks using lo cal approach and information diffusion. We investigate current algorithms and try to understand the limitations of them. We especially focus on high time-complexity of algorithms because of using global approach, i.e., try to optimize a global metric or perform computations regarding the whole network repeatedly. We propose new algo rithms using local approach (i.e., similarity based on common friends) and information diffusion (i.e., gossip spreading). Local approach uses locally available or computable information around a node to identify its community. With this, community detection task can be seen as a set of distributed and parallel tasks running simultaneously on different parts of the network. We also propose a variant of label propagation algorithm which decreases its overall execution time by eliminating unnecessary steps. During these studies, we develop a community detection framework which simplifies the task of defining, testing and comparing a new community detection algorithm.