Optimal partition and effective dynamics of complex networks

Abstract

Given a large and complex network, we would like to find the best partition of this network into a small number of clusters. This question has been addressed in many different ways. Here we propose a strategy along the lines of optimal prediction for the Markov chains associated with the dynamics on these networks. We develop the necessary ingredients for such an optimal partition strategy, and we compare our strategy with the previous ones. We show that when the Markov chain is lumpable, we recover the partition with respect to which the chain is lumpable. We also discuss the case of well-clustered networks. Finally, we illustrate our strategy on several examples.

Fig. 1.

The two clusters identified by our approach in Zachary's karate club network (36). The administrator and the instructor are represented by nodes 1 and 33, respectively. As initial condition for our k-means algorithm, we took random partitions. We obtained S₁ = {1 : 8, 10 : 14, 17, 18, 20, 22} and S₂ = {9, 15, 16, 19, 21, 23 : 34}, which is very similar to Zachary's actual observation: Only one node, node 11, is misclassified.

Fig. 2.

The mean fraction of correctly identified nodes versus the proportion of links towards the other communities. The four curves show the results of our k-means algorithm with 100, 300, 500, and 1,000 random initial partitions. As can be seen, the results improve as the number of initial conditions is increased, but the results eventually saturate (the curve with 500 trials can barely be distinguished below the one with 1,000 trials). The results show that our algorithm is among the very best of those compared in ref. .

Fig. 3.

The residual E* of the k-means algorithm obtained for 100 independent realizations of the ad hoc network with z_out = 8 using 100, 300, 500, and finally 1,000 random initial partitions. Also shown is the residual E* calculated with the known partition of the network. As can be seen, the actual residual E* identified by our k-means algorithm is often smaller than the one computed with the known community. This result reflects the very diffuse nature of the community structure in the ad hoc network when z_out = 8. The vertical lines on the graph act as a visual aid to identify the various points associated with the different realizations.