A Markov Chain-Based Overlapping Community Detection Algorithm for Complex Networks

Complex networks are extremely common in the world, ranging from protein interaction, biological organization to food chain. In a complex network, the cluster structure of nodes is known as the community structure [1]. The nodes in the same community are linked closer than those in different communities. It is necessary to fully understanding the cluster structure, before exploring the structure, evolution and predictive control of a complex network.

To analyze a complex network, an important basis is community detection [2], a.k.a. community discovery, which refers to the clustering of network nodes by algorithms. Unlike common clustering algorithms, community detection aims to find communities in the network graph. Community detection can be applied to various fields, including but not limited to knowledge mining, social network recommendation, and traffic flow optimization.

Judging by the formation of communities in complex networks, there are four types of community detections, namely, agglomerative detection, splitting detection, search detection and other detection. Specifically, agglomerative detection constructs the community gradually based on each network node; splitting detection considers all network nodes as a large community, and gradually split the large community into smaller ones; search detection integrates the previous two methods and pursues gradual optimization of the community structure.

Considering the above, this paper develops a novel overlapping community detection algorithm based on Markov chain. First, the input adjacency matrix was expanded and inflated to optimize the information flow and highlight the community boundary. Next, the matrix was normalized to obtain the transition probabilities of its elements. Then, an adaptive threshold was introduced to reconstruct the transition probability matrix. The reconstructed matrix was normalized column by column and used to detect the overlapping communities based on random walk and Markov chain.

3.1 Markov clustering (MCL) algorithm

The MCL [25] is a graph clustering method based on random walk and Markov chain. It is assumed that any walker that randomly enters a community is very unlikely to leave that community.

In the MCL, the random walk is essentially a process of changing the transition probability matrix of the Markov chain through expansion and inflation. The expansion operation is the limit distribution of the transition probability matrix. During the operation, the matrix is multiplied continuously to reach a stable state, that is, the information flows evenly in different regions of the network.

Meanwhile, the inflation operation is to perform power multiplication on each element of the matrix and then normalize the elements column by column. In this way, the strong correlations between the elements become stronger, and the weak ones become weaker. In other words, the information flows toward the attractor.

Through the alternation between the two operations, more and more information flows to the attractor, leading to the state convergence of transition probability matrix.

The basic process of MCL algorithm is as follows:

The MCL algorithm is suitable for weighted graphs, without needing the number of network communities. However, it cannot be directly applied to detect overlapping communities in large diameter networks.

To solve the problem, this paper reconstructs the transition probability matrix with an adaptive threshold, normalizes the reconstructed matrix column by column, and then adopts the normalized matrix to detect the overlapping communities based on random walk and Markov chain. The reconstructed transition probability matrix represents the complete graph, in which each overlapping node is displayed in its corresponding community. In other words, our approach ensures that the same community node has the same nonzero element position, rather than determine the nonoverlapping communities based on the nonzero element positions in the rows of the matrix.

3.2 Improved MCL based on random walk

To improve the MCL, the first step is to clearly define the random walk. As shown in Figure 1, the random walk is a process that a walker randomly moves from the starting point in a graph to any neighboring node. Then, the neighboring node becomes the new starting point for the next random movement. The random walk can be illustrated as a transition probability matrix, in which each element represents the state transition probability from row node i to column node j, and the total probability of each row adds up to one.

The transition probability matrix for the random walk in Figure 1 can be expressed as:

$P_{i j}=\left[\begin{array}{cccccc}{0} & {\frac{1}{2}} & {0} & {\frac{1}{2}} & {0} & {0} & {0}& {0} & {0} & {0} \\ {\frac{1}{2}} & {0} & {\frac{1}{2}} & {0} & {0}& {0} & {0} & {0} & {0} & {0}\\ {0} & {\frac{1}{2}} & {0} & {\frac{1}{2}}  & {0} & {0}& {0} & {0} & {0} & {0} \\ {\frac{1}{5}} & {0} & {\frac{1}{5}} & {0} & {\frac{1}{5}} & {0}& {\frac{1}{5}}& {\frac{1}{5}} & {0}& {0} \\ {0} & {0} & {0} & {\frac{1}{2}} & {0} & {\frac{1}{2}} & {0}& {0}& {0} & {0} \\ {0} & {0} & {0} & {0}& {\frac{1}{2}} & {0}& {\frac{1}{2}} & {0} & {0} & {0} \\ {0} & {0} & {0} & {\frac{1}{2}} & {0} & {\frac{1}{2}} & {0}& {0}& {0} & {0} \\ {0} & {0} & {0} & {0} & {\frac{1}{3}}& {0}& {0} & {0} & {\frac{1}{3}} & {\frac{1}{3}}\\ {0} & {0}& {0} & {0} & {0} & {0} & {0} & {\frac{1}{2}} & {0} & {\frac{1}{2}} \\ {0} & {0}& {0} & {0} & {0} & {0} & {0} & {\frac{1}{2}} & {0} & {\frac{1}{2}}\end{array}\right]$

1.png

Figure 1. An example of random walk

As shown in Figure 1 and the above matrix, a random walker at node 2 will move to node 3 or node 1 at the probability of 50%. The probability for him/her to move to any other node is 0. If the walker is at node 4, he/she will move to nodes 1, 3, 5, 7 or 8 at the probability of 20%. The probability for him/her to move to any other node is 0.

The next step is to clearly understand the Markov chain. The Markov chain is a stochastic process that satisfies the Markov property. The state of Markov chain at any moment only depends on that at the previous moment. Therefore, the future state is only related to the current state, rather than the past state, i.e. the past and the future states are independent of each other. The Markov property can be defined as:

$P\left(X_{t+1}=x | X_{1}=x_{1}, X_{2}=x_{2}, \ldots, X_{t}=x_{t}\right)=P\left(X_{t+1}=\right.\left.x | X_{t}=x_{t}\right)$    (1)

In actual practice, the input adjacency matrix cannot be directly used for expansion and inflation. Here, a self-loop is added to eliminate the influence of even and odd power on random walk. Besides, the nonzero matrix was normalized to determine the probability for a node by column number to transform into a node represented by row number.

The transition probability matrix thus obtained was expanded by e power. Then, each element in the matrix was inflated by r power. The expansion helps to complete the random walk, such as to spread the information carried by the network flow to the distance. The inflation attempts to enhance the intra-cluster correlation, and weaken the inter-cluster correlation, enabling the communities to separate from the network automatically.

If the matrix is directly normalized after expansion and inflation, the influence of overlapping nodes will be ignored. In fact, overlapping nodes with a large degree may act as attractors and affect community detection results. Therefore, a new network graph was generated by reconstructing the adjacency matrix through adaptive thresholding:

$e_{i j}=\left\{\begin{array}{ll}{1} & {e_{i j}>\operatorname{mean}(e)} \\ {0} & {e_{i j} \leq \operatorname{mean}(e)}\end{array}\right.$            (2)

After matrix reconstruction, the community structure in the network become clearer, and the community boundary become more obvious.

The final matrix was obtained through iterations until reaching the convergence state: the reconstructed matrices before and after the current iteration are consistent with each other. The final matrix is a 0-1 symmetric block matrix, which implies the community structure of the network. This matrix can be interpreted as follows:

The node represented by the row number of any diagonal nonzero element belongs to the same community as the node represented by the column number of other nonzero elements in the row vector.

If the community of the node represented by the column numbers of other non-zero elements in the row vector is not unique, the node belongs to different communities, that is, the node is an overlapping node.

If the other elements in the row vector are all zeros, then the node is an outlier.

Therefore, the final matrix obtained by our algorithm clearly reflects the partition of overlapping nodes. The vector of overlapping nodes in the matrix can be decomposed into the vector form of their communities.

3.3 Algorithm instance

From the network structure of Figure 1, the adjacency matrix of the network can be obtained as:

$\left[\begin{array}{llllllllll}{0} & {1} & {0} & {1} & {0} & {0} & {0} & {0} & {0} & {0} \\ {1} & {0} & {1} & {0} & {0} & {0} & {0} & {0} & {0} & {0} \\ {0} & {1} & {0} & {1} & {0} & {0} & {0} & {0} & {0} & {0} \\ {1} & {0} & {1} & {0} & {1} & {0} & {1} & {1} & {0} & {0} \\ {0} & {0} & {0} & {1} & {0} & {1} & {0} & {0} & {0} & {0} \\ {0} & {0} & {0} & {0} & {1} & {0} & {1} & {0} & {0} & {0} \\ {0} & {0} & {0} & {1} & {0} & {1} & {0} & {0} & {0} & {0} \\ {0} & {0} & {0} & {1} & {0} & {0} & {0} & {0} & {1} & {1} \\ {0} & {0} & {0} & {0} & {0} & {0} & {0} & {1} & {0} & {1} \\ {0} & {0} & {0} & {0} & {0} & {0} & {0} & {1} & {1} & {0}\end{array}\right]$

After setting the diagonal element of the adjacency matrix to 1, it is assumed that a node can stay in the local area with a certain probability without moving. For simplicity, the matrix is normalized column by column so that the sum of transition probabilities of any column is 1. Through normalization, the transition probability matrix can be obtained as:

$\left[\begin{array}{ccccccc}{\frac{1}{3}} & {\frac{1}{3}} & {0} & {\frac{1}{6}} & {0} & {0} & {0} & {0} & {0}  & {0}\\ {\frac{1}{3}} & {\frac{1}{3}} & {\frac{1}{3}} & {0} & {0} & {0} & {0} & {0} & {0} & {0}\\ {0} & {\frac{1}{3}} & {\frac{1}{3}} & {\frac{1}{6}}& {\frac{1}{3}} & {0} & {0} & {0}& {0} & {0}  \\ {\frac{1}{3}} & {0} & {\frac{1}{3}} &  {\frac{1}{6}}& {0}& {\frac{1}{3}} & {\frac{1}{4}} & {0} & {0} & {0} \\ {0} & {0} & {0} & {\frac{1}{6}} &{\frac{1}{3}} & {\frac{1}{3}}& {0} & {0} & {0} & {0} \\ {0} & {0}& {0} & {0} & {\frac{1}{3}} & {\frac{1}{3}} & {\frac{1}{3}} & {0} & {0} & {0}\\{0}& {0}& {0}& {\frac{1}{6}}& {0}& {\frac{1}{3}}& {\frac{1}{3}}& {0}& {0}& {0} \\ {0} & {0} & {0}  &  {\frac{1}{6}} & {0} & {0}& {0} & {\frac{1}{4}} & {\frac{1}{3}} & {\frac{1}{3}} \\ {0} & {0} & {0}& {0} & {0} & {0} & {0} & {\frac{1}{4}} & {\frac{1}{3}} & {\frac{1}{3}} \\ {0} & {0} & {0} & {0} & {0}& {0} & {0} & {\frac{1}{4}} & {\frac{1}{3}} & {\frac{1}{3}}\end{array}\right]$

The expansion parameter was set to 2, that is, the random walker only moves by one step in the network. The expansion was carried out by multiplying the transition probability matrix. The inflation parameter was set to 1, indicating that the matrix does not change but directly goes to the reconstruction phase. The reconstructed matrix can be expressed as:

$\left[\begin{array}{lllllllll}{1} & {1} & {1} & {1} & {0} & {0} & {0} & {0} & {0} & {0} \\ {1} & {1} & {1} & {1} & {0} & {0} & {0} & {0} & {0} & {0} \\ {1} & {1} & {1} & {1} & {0} & {0} & {0} & {0} & {0} & {0} \\ {1} & {1} & {1} & {1} & {1} & {1} & {1} & {1} & {0} & {0}  \\ {0} & {0} & {0} & {1} & {1} & {1} & {1} & {0} & {0} & {0} \\ {0} & {0} & {0} & {1} & {1} & {1} & {1} & {0} & {0} & {0} \\ {0} & {0} & {0} & {1} & {1} & {1} & {1} & {0} & {0} & {0} \\ {0} & {0} & {0} & {1} & {0} & {0} & {0} & {1} & {1} & {1} \\ {0} & {0} & {0} & {0} & {0} & {0} & {0} & {1} & {1} & {1} \\ {0} & {0} & {0} & {0} & {0}& {0} & {0} & {1} & {1} & {1}\end{array}\right]$

2.png

Figure 2. Reconstructed network structure

The mean of all elements of the reconstructed matrix was taken as the adaptive threshold, and used to compare and reset the elements of that matrix. In this way, a new adjacency matrix was obtained, which corresponds the network structure in Figure 2.

In the reconstructed network, the intra-cluster connections are denser than the original network, while the inter-cluster connections are sparser than before. Hence, the information of the overlapping nodes is well preserved.

The reconstruction was carried out through continuous normalization, expansion and inflation operations until two successive iterations output the same reconstructed matrices. Hence, the final matrix can be expressed as:

$\left[\begin{array}{llllllllll}{1} & {1} & {1} & {1} & {0} & {0} & {0} & {0} & {0} & {0} \\ {1} & {1} & {1} & {1} & {0} & {0} & {0} & {0} & {0} & {0} \\ {1} & {1} & {1} & {1} & {0} & {0} & {0} & {0} & {0} & {0} \\ {1} & {1} & {1} & {1} & {1} & {1} & {1} & {0} & {0} & {0} \\ {0} & {0} & {0} & {1} & {1} & {1} & {1} & {0} & {0} & {0} \\ {0} & {0} & {0} & {1} & {1} & {1} & {1} & {0} & {0} & {0} \\ {0} & {0} & {0} & {1} & {1} & {1} & {1} & {0} & {0} & {0} \\ {0} & {0} & {0} & {0} & {0} & {0} & {0} & {1} & {1} & {1} \\ {0} & {0} & {0} & {0} & {0} & {0} & {0} & {1} & {1} & {1} \\ {0} & {0} & {0} & {0} & {0} & {0} & {0} & {1} & {1} & {1}\end{array}\right]$

For any element in the final matrix that equals 1, the nodes represented by the row and column of that element belong to the same community. Obviously, if there is a block in which all elements are 1 in the final matrix, then the corresponding nodes all belong to a community. If there is an intersection of such blocks, the nodes in the intersection are the overlapping nodes belonging to different communities.

As shown in Figure 3, the different color regions represent different communities in the new network. The node (4) covered by more than one color region is an overlapping node that belong to two public communities.

3.png

Figure 3. Results of overlapping community detection

This paper puts forward a random walk algorithm based on Markov chain for overlapping community detection in complex networks. The proposed algorithm transfers information, enhances intra-cluster connections and highlights the community boundary through expansion and inflation. The adaptive threshold was introduced to reconstruct the network to facilitate the mining of overlapping communities. The effectiveness of our algorithm was fully demonstrated through experiments on artificial and real-world networks. The future research will further enhance the applicability of our algorithm to real-world complex networks.