On the Spectral Characterization and Scalable Mining of Network Communities
|Name||On the Spectral Characterization and Scalable Mining of Network Communities|
Network communities refer to groups of vertices within which their connecting links are dense but between which they are sparse. A network community mining problem (or NCMP) is concerned with the problem of finding all such communities from a given network. A wide variety of applications can be formalized as NCMPs, ranging from social and/or biological network analysis to Web mining and searching. So far many algorithms addressing the NCMP have been developed and most of them fall into the categories of either optimization based or heuristic methods. Distinct from the existing studies, the work presented in this paper explores the notion of network communities and their intrinsic properties from the dynamics of a stochastic model naturally introduced. In the paper, a relationship between the hierarchical community structure of a network and the local mixing properties of such a stochastic model has been established with the large deviation theory. Critical topological information regarding to the community structures hidden in networks can be inferred from their spectral signatures. Based upon the above-mentioned relationship, this work proposes a general framework for characterizing, analyzing, and mining network communities. Utilizing the two basic properties of metastability, i.e., being locally uniform and temporarily fixed, an efficient implementation of the framework, called the LM algorithm, has been developed that can efficiently mine natural communities hidden in networks with scalable performances. The effectiveness and efficiency of the LM algorithm have been theoretically analyzed as well as experimentally validated.
|ieee paper year||2012|