{'fraction_non_alphanumeric': 0.029895602657386902, 'fraction_numerical': 0.008763049667826638, 'mean_word_length': 4.969971671388102, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Fast Overlapping and Hierarchical Community Detection via Local Dynamic Interaction

Community structure has many practical applications and identifying communities could help us to understand and exploit networks more effectively. Generally, real-world networks include several different kinds of nodes which are general cluster nodes within communities, as well as some special nodes like hubs and outliers. In addition, real-world networks often have a hierarchical structure with communities embedded within other communities. However, there are few effective methods can identify these structures. This paper proposes an algorithm (OHELPA) to detect overlapping and hierarchical communities, which also can find hubs and outliers. OHELPA is based on coreness centrality to update nodes' possible community labels, and uses communities as nodes to building new network. By repeat the procedure, the proposed algorithm can effectively reveal the overlapping and hierarchical community structure in large scale networks. Moreover, it overcomes the high complexity and poor applicability problem of similar algorithms. To illustrate our methodology, we conduct experiments with real-world networks for community detection, and compare with many other classic methods. Experimental results demonstrate that OHELPA achieves excellent performance.


Introduction
Communities are groups in which the nodes are more likely connected to each other than to the rest of the network. Community structure is a common feature of many networks [1], including social network [2], biological networks [1], transportation networks [3],disease network [4], etc. There are many large-scale real-world complex networks whose structure is not fully understood. Identifying the community structure is crucial to reveal abundant hidden information and could help us to understand the functional properties of the networks.
In the last decade, network science has attracted much attention, and many methods have been proposed to detect the communities of complex networks [5][6][7][8][9][10][11][12][13][14][15][16][17][18][19][20][21]. Division methods are finding inter-community edges and remove them from the network [5,6], agglomerative methods are iteratively merge communities according to certain given measurement [7], and optimization approaches are based on the maximization of the modularity of network partition [8,9]. Recently, matrix related methods (nonnegative matrix factorization [10,11], spectral method [12] ) and model based methods (label propagation methods [13][14][15], mixture models [16], Stochastic block models [17,18] ) have also been presented for community detection. Label propagation algorithms (LPA) [13] is one of the fastest community detection algorithms, and it has nearly linear time complexity. In the era of big data, LPA based community detection algorithms have significant advantage in large networks. Moreover, importance measure [22][23][24] is key to quantify nodes' spreading capability in complex networks and also important to evaluate nodes' influence and insure LPA based algorithms' stabability. In addition, communities of real-world networks are usually overlapping and hierarchical, and some overlapping and hierarchical community detection methods also are proposed [19][20][21]. However, up to now, most community detection methods have limitations, and there still have huge demand for developing more general approaches.
Besides the general nodes that are densely connected within communities, there are some special nodes like hubs bridging multiple communities and outliers that are marginally connected with a community, which play important role in real-world networks. For example, hubs in computer network could be routers and in epidemiology could be central nodes for spreading diseases. These nodes should be considered as hubs that are closely related to different communities, forming overlapping communities. Recently, some researchers try to identify communities as well as hubs and outliers altogether [32,33]. Therefore, how to detect overlapping and hierarchical communities as well as hubs and outliers in a network becomes an interesting and challenging problem.
In this work, we propose a fast overlapping and hierarchical community detection algorithm (OHELPA) based on local dynamic interaction. The main contributions are summarized in the following: 1. We enhance the performance of NIBLPA [14] by computing node influence based on coreness centrality [22] , and through which the algorithm consider both networks' local and global information, and changing the order of node updating and the label choosing mechanism. 2. In face of real-world networks' overlapping and hierarchical structure, we allow each node belong to multiple communities and replacing the communities identified in last round by super-nodes in super-network to find overlapping and hierarchical communities. 3. We compare our algorithms with LPA [13], NIBLPA [14], Newman Fast Algorithm (NF) [46], EAGLE [21], and Louvain method [9]. Experiments show that OHELPA does not only reveal the meaningful communities more effectively than other methods in real-world networks, but also identify the hubs and outliers. 4. OHELPA overcomes the high complexity and poor applicability problem of similar algorithms, it can effectively find the communities with various densities and properties, such as clique dominated networks and sparse networks (Most real-world network data is sparse). OHELPA can accurately describe the subordinate degree of nodes to every related communities based on the ratio of label influences.
Following parts are organized as follows. Section 2 introduces the related community detection methods. We introduce our extended neighborhood coreness centrality based LPA (ELPA) in Section 3.1 and hierarchical community detection algorithm (HELPA) in Section 3.2. In Section 4 provides detection method OHELPA and complex analysis. The data description and evaluate criteria are presented in Section 5.1, and the effectiveness of our methods are respectively discussed in Sections 5.2, 5.3 and 5.4. Conclusions are given in Section 6.

Related works
As the network size becomes larger and larger and communities are usually overlapping and hierarchical in real world applications, fast algorithms and overlapping and hierarchical community detection methods are in demand. Many methods have been proposed for community detection problem in literature [26,27], here we only mention some new results that closely relate to us.
In order to rapidly find community structure in large networks, LPA [13] initializes each node with a unique label and at every step each node adopts the label that most of its neighbors currently have, which changes the global community detection problem into a local label selection problem, and groups of connected nodes with same label form communities. The node influence based LPA [14] improves the performance of LPA by improving the node orders of label updating and the label selection mechanism, but it consider the non-overlapping case only and the parameter  is difficult to tuning. Peng et al. [28] found that K-core may be much smaller than the original graph while retaining its community structure. The paper first finds communities in K-core and then inferring community labels for the remaining nodes to accelerate community detection. But the parameter K depends on community detection algorithm and data sets, only an appropriate K can reduce the running time while preserving the detection quality, and K-core may not retain original graph's community structure in sparse real-world networks. Huang et al. introduce a new quality function of local community and present a fast local expansion algorithm for uncovering communities in large-scale networks [29]. Meanwhile, in older to accelerate algorithms' speed, multi-threaded and parallel algorithms are introduced as well [30,31].
Blondel et al. [9] proposed a simple method for hierarchical community detection in complex networks. The method assigns each node to a different community and merges communities based on modularity optimization, then builds a new network whose nodes are the communities found in the last step. The algorithm repeats the process and uncovers community structure in different level of organization. LPA based overlapping community detection method was presented by Gregory et al. [15], the method assigns each node to communities through label propagation and each node can belong to v communities, where v is the parameter of the algorithm. Huang et al. [32] and Cao et al. [33] proposed methods which are capable of identifying communities as well as hubs and outliers simultaneously. Albeit all of overlapping communities, hierarchical structures as well as hubs and outliers detection are well studied in last several works, they are not furnish them together.
In addition, Lancichinetti et al. [20] make a pioneering attempt on finding overlapping and hierarchical community structure simultaneously in complex networks. The method searches natural community of node iteratively based on the local optimization of a fitness function. The procedure enables each node to be included in more than one module, leading to a natural description of overlapping communities. The method can uncover the hierarchical relation between these overlapped communities by tuning the resolution parameter  . Shen et al. [21] also proposed a overlapping and hierarchical community detection algorithm, which adopts an agglomerative framework to deal with a set of maximal cliques. The algorithm defines a community similarity measure to construct a dendrogram, and uses a extended modularity to cut the dendrogram. The algorithm is limited by its assumption that the network has a large number of cliques.
In this paper, we propose an algorithm (OHELPA) to detect overlapping and hierarchical communities, which also can find hubs and outliers.

ENCoreness based LPA (ELPA) (1) Algorithm
The updating order of nodes and label selection mechanism play crucial impact on the stability and quality of LPA based algorithm. Generally, NIBLPA [14] adopts k-shell [23] to measure node importance and compute node influence, and arranges nodes in descending order of node influence to update community label. A parameter  from 0 to 1 is used to adjust the effect of its neighbors on the influence of node i . We analyze the NIBLPA and find that: a. k-shell decomposition assigns many nodes with identical k-shell index, although the importance of the nodes in the same shell may differ from each other. It only consider nodes' global information (coreness value) but neglects nodes' local information (node degree), and can not precisely distinguish nodes' importance.
b. The descending node order may lead to inaccurate label information of the core nodes which located in networks' topology center be diffused and propagated in each rotation, and the core nodes' label importance would also be magnified compared to broder node. c. The tunable parameter  from 0 to 1, which is used to adjust the impact strength of neighbors to current node's influence. There are many available values for parameter  to choose, and the appropriate  only be determined according the data sets, which results in NIBLPA's poor applicability in practical applications. We adopt extended neighborhood coreness (ENCoreness) centrality [22] to estimate the influence of a node, which consider the degree and the coreness simultaneously and assume that the node with more connections to the neighbors located in the core of the network is more powerful. Meanwhile, we update community label in ascending order of node influence, and the parameter  in our algorithm is much more simplified.
The node influence of node i is defined as follows: ( ))} sqrt degree j , which also means the label information's importance and diffusion scope (the more label importance, the more greater diffusion scope). In most cases, 1   is appropriate.
The node i 's community label is updated as equation (2), we calculate the influence of each label l in the possible label set L , and assign the label with the greatest influence to node i .
or else equals to 0, other notations have same meaning as in equation (1). According to equation (2), node selects the the most influential label of neighbors as their new label.
The pseudo-code of ELPA is presented in Algorithm 1, the main process can be divided into two stages. In the first stage, we compute node influence according to equation (1) and arrange node in order. In the second stage, nodes update their label according to equation (2) in order of influence ascending. Repeat this step until no node's label changes. The illustration of this procedure can be seen in Figure 1.
(2) Calculate NI and node order: compute node influence ) (i NI according to equation (1) and arrange nodes in ascending order, then store the order and ) (i NI set in vector X and NI . (3) Iteration of label propagation:

(2) Discussion
Through observation of LPA based community detection algorithm, we conclude that LPA is a flexible framework for clustering network nodes, and outstanding LPA related algorithms need obey three fundamental rules.

Rule 1. Design the calculate method of node influence and label influence reasonably, and maintain the balance of the core nodes and broder nodes' label influence.
The ENCoreness value of core nodes which are always have higher degree and k-shell value are always bigger than other nodes'. If we use a unreasonable method to calculate node influence, such as , then the core nodes' influence would much greater than border nodes', and if we use to calculate label influence simultaneously, then the label's influence of core nodes will much greater than the label's influence of border nodes, even the label's influence of core nodes could be many orders of magnitude greater than the label's influence of border nodes. In these cases, although some node connects to many border nodes and few core nodes, the node would select one of core nodes' label as its new community label rather than border nodes' label. After this method is repeated iteratively, all network nodes may tends to a same label choice, and community detection result presents a "identity" phenomenon. Reversely, if labels' influence are similar, each network node may tends to a specific label choice, and community detection result presents a "fragments" phenomenon.

Rule 2. Updating node community label in the ascending order of node influence value.
There are more nodes select label based on core nodes' label than based on border nodes' label, so the core nodes' label should be selected based on all nodes' label information, that is selecting core nodes' label after all other nodes' labels are decided, so make the core nodes' label as accurately as possible. Else, the core nodes' inaccurate label information will be diffused and propagated in each iteration, and disturb other nodes' label selection. On the other hand, updating node label in the descending order would make several core nodes share a same label before updating border nodes' label, which may further amplify core nodes' label importance and lead to all network nodes may tends to a same label choice Rule 3.

Considering nodes' global role in network and its local topology information comprehensively.
k-shell method assigns identical k-shell value to nodes with difference influence, which just consider nodes' topology location and neglects nodes' degree, so it can not precisely estimate nodes' influence. Node importance should consider its coreness, neighbor nodes number and their importance simultaneously, just such importance measure based node influence is precise.

Hierarchical ENCoreness based LPA (HELPA)
Although we proposed a more efficient and simplified community detection algorithm ELPA including a parameter with three candidate values, it is still confusing to some users how to choose a appropriate parameter value. Meanwhile, many real-world networks have hierarchical structure, so we propose a hierarchical community detection algorithm HELPA based on ELPA.
In HELPA, the first phase is conducting ELPA in network to find communities, and then building a super-network by replacing initial communities with super-nodes in the second phase. These two phases are executed iteratively to construct a dendrogram until there is no node's label is changed. This process is illustrated in Figure 2. The height of the dendrogram is determined by the number of iteration and is generally a small number. In this algorithm, is appropriate to most of networks, the possible "fragments" phenomenon would be circumvented thanks to the intrinsic multi-level nature of our algorithm. HELPA could find different size of communities at every level, and finally recommend the best community detection result to users based on modularity maximization [8]. Given a community set , the modularity measure Q is defined as follows: the sum of degree of nodes in community v , M is the number of edges of the whole network.
The pseudo-code of HELPA is presented in Algorithm 2.
Such a process of building super-network is shown in Figure 3. Figure 3 (a) is the communities detected by ELPA. In Figure 3 (b) built by method 1, the edges' weight is the number of edges between communities in Figure 3 (a), and the weight of self-loop is the number of edges of the responding community in Figure 3 (a), we find that the weight of edges is much lower than the weight of self-loops, although the density of the edges between communities is similar with the density of the edges in communities in Figure 3 (a). The degree of community merging based on method 1 is smaller, and the algorithm's convergence speed is slow. The result of method 2 (Figure 3 (c)), in which the weight of edges and self-loops is the number of edges divides the number of the related nodes, shows that the ratio between the weights of edges and self-loops approximates the ratio between the densities of the responding edges in Figure 3 (a). Hence we argue that method 2 has a higher degree of merging and a faster convergence speed in building super-network than method 1.
. Copy the network G and its label set to network SG .

Overlapping and Hierarchical ENCoreness based LPA (OHELPA)
In the overlapping ENCoreness based LPA method , the node influence of node i is defined as same as equation (1). For overlapping community detection, the node i 's available community labels and their influence are calculated as follows: where j C is the community label set of node j , and l LI is the influence of label l , other notations have same meaning as in equation (2).
is weight ratio of label l to all labels.
By using the ratio to update node label, the calculation will be more accurate.
According to equation (4), we can get all possible labels i LIS of node i . Then, we find the most influential labels in i LIS as node i 's label set i C . Inspired by the regularization and sparsity, we perform cute operation on labels' influence and find the labels with the same order of magnitude with the greatest label influence in i LIS as follows: In order to find the the best overlapping community division, we use extended modularity (EQ) [8] to evaluate the overlapping community detection results. Given a cover of the network, the extended modularity (EQ) [8] is defined as follows: where c n is the number of communities, vw A is the element of adjacency matrix of network, it takes value 1 if there is an edge between vertex v and vertex w and 0 otherwise. m is the total number of edges in the network. v k is the degree of node.
In OHELPA, the initial phase is to detect overlapping communities according to equation (4), (5), and the second phase is building a weighted super-network, and perform ELPA on the network to detect non-overlapping communities (there is no overlapping nodes in super-network as the nodes represent the communities of initial network). Repeating the second phase and save the result to construct a dendrogram until there is only one community remained. In OHELPA, the possible "network fragments" will be clustered by the ELPA on the higher level of super-network. The pseudocode of OHELPA is presented in Algorithm 3. OHELPA could find different size of communities at different level, and recommend the best overlapping community detection result with the greatest EQ to users. Build super-network: because of some nodes may belong to more than one communities, building super-network based on overlapping communities is different from the method based on non-overlapping communities shown in section 3.2, the weight , i j w is defined as equation (8) and the process of building super-network is illustrated in Figure 4.
(2) Overlapping ENCoreness based LPA to find initial overlapping communities: (a) Calculate NI and node order: Set 0 t  , compute node influence ) (i NI according to equation (1) and arrange nodes in ascending order, then store them in vector NI and X .

Experiment
In this section, we demonstrate that, on real world data, our approaches can find non-overlapping communities, overlapping and hierarchical communities effectively, while it can find hubs and outliers, and it has general applicability and low time complexity. We use modularity and extended modularity as the quality measurement. We compare our algorithms with LPA [13], NIBLPA [14], Newman Fast Algorithm (NF) [46], EAGLE [21], and Louvain method [9]. Our algorithms are implemented in Python 2.7 and Networkx 1.9. All the experiments we conducted on a virtual machine with Ubuntu 12.04 and 2GB of RAM. The code of our algorithm is freely available for download on the webpage [25].

Datasets and Algorithms
To access the performance of the proposed methods, we use the real world datasets from Mark Newman's Network Datasets 1 and The Koblenz Network Collection 2 , as shown in Table 1. The related methods are introduced as follows: LPA: initializes each node with a unique label and select node randomly to update its label according to its neighbors' label NIBLPA: initializes each node with a unique label and update node's label according to its neighbors' label in descending order of NI. NF: initializes each node as a community, and merges communities to construct dendrogram based on modularity gain maximum until only one community left, and cut the dendrogram to get the best community division.
EAGLE: finds all maximal cliques with the size bigger than k , and construct dendrogram based on community similarity, then cut the dendrogram using extended modularity to find communities. Louvain method: initializes each node as a community and merge nodes based on modularity gain, then considers each community as a node to repeat the merge process.

Experimental Results and Analysis
In this section, we evaluate the performance of our method with 13 different types of real-world networks under the three conditions: non-overlapping cases, hierarchical cases and overlapping and hierarchical cases. The size of the networks spans tens to tens of thousands of nodes. We consider the accuracy, speed and applicability of algorithms.  We compared the ELPA with LPA, NIBLPA using modularity measurement, and the results are in Table 2. It can be seen from Table 2 that LPA is unstable for community detection, and the results of LPA are inconsistent, as the second column shows, which have different communities with different modularity on the same networks. Moreover, the communities detected by LPA are unreasonable and are not consist with that real community structure, as Figure 4  We can find that LPA is instable on real-world networks, and the results detected by LPA on the same network are different, which is inapplicable in solving practical problems.

(1) Evaluation in non-overlapping cases
Comparing with LPA and NIBLPA, the modularity of communities detected by ELPA in all networks except Euroroad and Facebook is higher than the other algorithms. Figure 6 are the results of ELPA on Dolphins and Facebook datasets, we can find that our algorithm can reveal the community structure excellently. Simultaneously, the stability of ELPA is better than LPA. In general, ELPA can get better and stable results that the other algorithms. (2) Evaluation considering hierarchical structure It has been shown that communities of real-world networks always are hierarchical. We proposed HELPA based on ELPA by constructing super-networks, and find possible communities in all level of network. We compared the HELPA with NF and Louvain using modularity measurement, and the results are in Table 3. It can be seen from Table 3 that Louvain algorithm find the highest modularity in most of networks, and our method HELPA acquires nearly the same modularity value. From Table 4, we find that HELPA need more time to detect communities comparing NF and Louvain methods. Table 3: The analyze of real-word networks in hierarchical cases In addition, we find that modularity measurement is not accurate and reasonable for all condition, and the communities division with the greatest modularity may be not the real communities. For example, in the Figure   Based on the above analysis, we argue that we should compare our results with real communities, besides using modularity to evaluate. If the experiment results are carefully analyzed, we can find that the number of the communities detected by Louvain is always greater than the number of real communities, the second column of Table 3  In method 1, the edges' weight is the number of edges between communities, and comparing method 2, the merging degree and the difference of communities' size between adjacent iterations is smaller. Based on method 1, HELPA can find embedded communities more elaborate. The disadvantage is that maybe we can not find larger communities in higher level. From Figure 7 (a), (b) , (c), we know that HELPA detects communities in 3 levels based on method 1, and it can not find larger communities, such as Figure 7 (d). In method 2, the edges' weight is the number of edges divides the number of the related nodes, and the merging degree and the difference of communities' size between adjacent iterations is greater. We can not find larger communities in higher level based on method 2, but we may skip the communities with more modularity in immediate level. From Figure 7 (a), 6 (d), we know that HELPA detects communities in 2 levels based on method 2, and skips some levels, such as Figure 7 (b). We recommend users to use method 2 in large networks, and use method 1 in small and medium-sized networks.
Analysis of the resolution limit problem: Despite the modularity measure is widely used to evaluate the communities result on many practical networks, it may ineffectively in some cases. It has been show that modularity contains an intrinsic scale which depends on the number of links of the network, and those modules smaller than that scale may not be resolved, even if they were complete graphs connected by single bridges. The resolution limit of modularity actually depends on the degree of interconnectedness between pairs of communities and can reach values of the order of the size of the whole network [47].
(a) Ring 2 (b) Ring 1 and the communities found by Louvain In Figure 8 (a), we show a network consisting of a ring of several cliques, connected by single links, each clique is a complete graph with n nodes. We assume that there are c cliques. According to [47], modularity based methods would lead to a partition where the cliques are combined into groups of two or more, as the results in Figure 8 (b) (communities are denoted by dotted lines). We analyze three types of Ring datasets, and the results are shown in Table 5, where n is the number of nodes in each clique, and m is the total number of edge in each Ring, and c is the correct number of communities. The results show that NF and Louvain methods can not find correct communities in Ring networks, and our algorithm HELPA is outperform them.

(3) Evaluation in overlapping cases considering hierarchical structure
Real-world networks always have overlapping communities and hierarchical structural. We proposed OHELPA based on HELPA by allowing each node belongs to more than one community and finding possible communities in all level of network. We compared the OHELPA with EAGLE using extended modularity measurement, and the results are in Table 6 and Table 7 (As EAGLE needs too long time for community detection, and we only list the results in small size network). It can be seen from the results that OHELPA are outperform EAGLE in either efficient or effect. OHELPA can find nearly real communities in a relatively short period of time.
The problem of EAGLE is that it is based on maximum cliques, and need compute similarity between each pair of communities, so it need more time and only has excellent performance in clique dominated networks, however, most of real-networks are sparse, and many cliques only have one node. Hence, EAGLE has a poor efficiency and tends to find more communities with smaller size in real-world networks.    Figure 10 are the community detection results of EAGLE and OHELPA in schematic network dataset and dolphins. From Figure 9, we know that schematic network is a clique dominated network, and EAGLE reveal a very reasonable communities result, and the overlapping nodes are also rational. Simultaneously, our method OHELPA detects a parallel result. Moreover, OHELPA can present the degree that each overlapping node belongs to every related community, for example, the overlapping nodes and their community degree found by OHELPA is: In addition to detect the overlapping communities and the hierarchical structure, we argue that OELPA also can find hubs and outliers. The result of OHELAP in NetSciSub is presented in Figure 11. The hubs are marked by red boxes, such as node 71, and outliers are marked by red circles, such as node 1556, 1557, and 1558. Based on the above analysis, we can conclude that ELAP outperforms LPA and NIBLPA in non-overlapping cases, and HELPA has a better performance than NF and has a nearly same capability with Louvain method considering hierarchical structure, and OHELPA outperforms EAGLE in overlapping cases considering hierarchical structure. In addition, we found that Louvain method has resolution limit problem and EAGLE is unsatisfactory in real-world networks.
So, OHELPA has better performance in community accuracy, speed and applicability than other algorithms.

Conclusions
In this paper, we present a fast overlapping and hierarchical community detection algorithm (OHELPA) based on local dynamic interaction. Based on local network information, the proposed algorithm can effectively reveal the embedded hierarchical and overlapping communities in complex network, and can identify hubs and outliers as well. It does not have the resolution limit problem and can find communities in all kinds of networks. Experiment results show that our algorithm achieve a better performance than other similar algorithms. Nevertheless, our method is not perfect, we need faster algorithm to detect communities in large networks, and we plan to explore data compression methods and parallel algorithms. In addition, we want to apply our method to realistic problems, and improve the modularity measurement to more evaluate community detection results more accurately.