Multiscale Community Detection in Networks with Heterogeneous Degree Distributions
Graph clustering has been widely applied in exploring regularities emerging in relational data, e.g., community detection. Most existing methods investigate the community structure at a single topological scale. However, community structure of real world
- PDF / 610,761 Bytes
- 27 Pages / 439.37 x 666.142 pts Page_size
- 97 Downloads / 245 Views
Multiscale Community Detection in Networks with Heterogeneous Degree Distributions
3.1 Introduction Graph clustering has been widely applied in exploring regularities emerging in relational data. Recently, the rapid development of network theory correlates graph clustering with the detection of community structure, a common and important topological characteristic of networks. Most existing methods investigate the community structure at a single topological scale. Furthermore, the detection of multiscale community structure is heavily affected by the heterogeneous distribution of node degree. Thus, it is very challenging to detect multiscale community structure in networks with heterogeneous degree distribution. In the past decade, many methods have been proposed to investigate the community structure in networks [1–3]. These methods identify the community structure through finding an optimal partition of network according to certain criterion or definition of community. In general, the identified community structure corresponds to only one topological scale of network. However, as shown by empirical studies, the community structure of real world networks often exhibits multiple scales [4–7], i.e., more than one topological description is beneficial to characterize the community structure of networks. Thus, it is desired to find methods that can detect multiscale community structure. Several studies have been conducted to investigate multiple topological scales of networks. Arenas et al. [8] pointed out that synchronization process on networks reveals topological scales of networks and that the spectrum of the Laplacian matrix can be used to identify such topological scales. In Ref. [9], we have used the network conductance to identify multiple topological scales through investigating the diffusion process taking place on networks. Delvenne et al. considered multiscale community structure through investigating the stability of graph communities across time scales [10]. A recent work gave a general optimization framework for the detection of community structure in multiscale networks [11]. Another work considered multiscale community structure through investigating the communities of links instead of communities of nodes [12]. H.-W. Shen, Community Structure of Complex Networks, Springer Theses, DOI 10.1007/978-3-642-31821-4_3, © Springer-Verlag Berlin Heidelberg 2013
45
46
3
Multiscale Community Detection in Heterogeneous Networks
However, there are still severe challenges that are not handled by previous work. Existing work does not consider the heterogeneity of node degrees, which is very common to real world complex networks in nature and society. Moreover, it is still an open problem on how to characterize the significance of different relevant topological scales of a complex network. To address these challenges, we consider the detection of multiscale community structure by introducing a novel framework based on dimensionality reduction. Intuitively, we view the standard representation of network topolo
Data Loading...
