Uncovering and testing the fuzzy clusters based on lumped Markov chain in complex network

Abstract

Identifying clusters, namely groups of nodes with comparatively strong internal connectivity, is a fundamental task for deeply understanding the structure and function of a network. By means of a lumped Markov chain model of a random walker, we propose two novel ways of inferring the lumped markov transition matrix. Furthermore, some useful results are proposed based on the analysis of the properties of the lumped Markov process. To find the best partition of complex networks, a novel framework including two algorithms for network partition based on the optimal lumped Markovian dynamics is derived to solve this problem. The algorithms are constructed to minimize the objective function under this framework. It is demonstrated by the simulation experiments that our algorithms can efficiently determine the probabilities with which a node belongs to different clusters during the learning process and naturally supports the fuzzy partition. Moreover, they are successfully applied to real-world network, including the social interactions between members of a karate club.

Figure 1. Lumped markov process of a network.

For a given partition on a network , we define a lumped network by aggregating all nodes belonging to a subset into a meta-node. The new weights are computed via weight averaging the transition probabilities between nodes and –, and the lumped Markov chain with transition probabilities can also be obtained.

Figure 2. The pdf of and for the given ad hoc network with 128 nodes and .

The solid lines and dashed lines represent the pdf of and respectively. In each figure, the lower peak corresponds to the nodes in this cluster, and the higher peak corresponds to the other nodes outside of this cluster.

Figure 3. The convergence history of the objective function during 5–30 iterations of the karate club network.

Figure 4. The visualization of the partitioning results of the karete club network.

(a)Hard partition with thresholding operation according to the node's maximal weight. (b)Hard partition by k-means in ; (c)Fuzzy partition by CGP2.