Detecting the Overlapping and Hierarchical Community Structure in Networks
Empirical studies indicate that communities in real world networks are simultaneously overlapped and hierarchical. This implies that one node can participate in more than one community simultaneously and community further contains sub-communities. However
- PDF / 892,713 Bytes
- 26 Pages / 439.37 x 666.142 pts Page_size
- 33 Downloads / 240 Views
Detecting the Overlapping and Hierarchical Community Structure in Networks
2.1 Introduction As described in the previous chapter, community structure is a common and important topological characteristic of many real world complex networks. Examples include the World Wide Web, citations networks, various kinds of social and biological networks, and many others [1–3]. In the past decade, community structure has attracted much research attention from various scientific fields since it is crucial to understand the structural and functional properties of networks [4–6]. Many methods have been proposed to identify the community structure of complex networks [7–13]. The reader can refer to Ref. [14] for reviews. These existing methods can be roughly classified into two categories in terms of the form of their results, i.e., to form a partition or a cover of the network. The first kind of methods produce a partition, i.e., each node belongs to one and only one community and is regarded as equally important. Different from classical graph partition problem, the number of communities and the size of each community are prior unknown. Among this kind of methods, the most successful ones are the methods based on the optimization of modularity [11, 15, 16], which is proposed by Newman et al. as a quality function to measure the goodness of a network partition [9]. A high value of modularity indicates a significant community structure. Generally, this kind of methods is suitable to understand the community structure of the whole networks, especially for the networks with small sizes. However, the modularity optimization methods also suffer several problems, e.g., the resolution limit problem [17, 18]. These problems pose concerns about the reliability of the community structure detected by directly optimizing the modularity. The second kind of methods aim to discover the node sets i.e., communities with a high density of edges. In this case, overlapping is allowed, that is, some nodes may belong to more than one community. Meanwhile, some nodes may be neglected as subordinate nodes. Therefore, these methods result in an incomplete cover of the network. Compared to the partition methods, this kind of methods are appropriate to find the cohesive regions in the large scale networks. Ever since the problem of detecting overlapping community structure is proposed by Palla et al., many methH.-W. Shen, Community Structure of Complex Networks, Springer Theses, DOI 10.1007/978-3-642-31821-4_2, © Springer-Verlag Berlin Heidelberg 2013
19
20
2 Detecting the Overlapping and Hierarchical Community Structure
ods have been proposed [8, 19–26]. In [8], the community structure is uncovered by k-clique percolation and the overlaps between communities are guaranteed by the fact that one node can participate in more than one clique. However, the k-clique method gives rise to an incomplete cover of network, i.e., some nodes may not belong to any community. In addition, the hierarchical structure cannot be revealed for a given k. In [24], by int
Data Loading...
