Community Detection Through Optimal Density Contrast of Adjacency Matrix

Article type: Research Article

Authors: Liang, Tianzhu | Szeto, Kwok Yip

Affiliations: Bioengineering Program, Hong Kong University of Science and Technology, Physics Department, Hong Kong University of Science and Technology, Clear Water Bay, Kowloon, Hong Kong, E-mail: henryltz@gmail.com, phszeto@ust.hk

Abstract: Detecting communities in real world networks is an important problem for data analysis in science and engineering. By clustering nodes intelligently, a recursive algorithm is designed to detect community. Since the relabeling of nodes does not alter the topology of the network, the problem of community detection corresponds to the finding of a good labeling of nodes so that the adjacency matrix form blocks. By putting a fictitious interaction between nodes, the relabeling problem becomes one of energy minimization, where the total energy of the network is defined by putting interaction between the labels of nodes so that clustering nodes that are in the same community will decrease the total energy. A greedy method is used for the computation of minimum energy. The method shows efficient detection of community in artificial as well as real world network. The result is illustrated in a tree showing hierarchical structure of communities on the basis of sub-matrix density. Applications of the method to weighted and directed networks are discussed.

Keywords: community detection, node clustering, energy minimization, greedy method, sub-matrix density, hierarchical structure

Journal: Informatica, vol. 22, no. 1, pp. 135-148, 2011