> By Thomas Aynaud and Jean-Loup Guillaume
To study the communities dynamics and stability, we have taken a network representing the co-authorship of scientists on www.arxiv.org and we have successively removed one random node and kept the biggest connected component. At each step, we have detected the communities in two ways. We have, first, used directly the louvain method to detect communities independently at each step. And second we have used it at each step, with an initialization using the previous step. We then compare, for each way, the partitions obtained at one step with the previous one.
Comparing two partitions is difficult, and existing parameters such as mutual information are difficult to interpret. To have a more intuitive measurement, we computed the number of transformations needed to change one partition to the other. Each part of the first partition is assigned to one part of the second (we add empty parts if needed to have a complete matching) , and the cost of the full assignment is the number of nodes which are misplaced, i.e which belong to one part of the first partition and not to the assigned part of the second. Of course, there are many possible assignments, so we compute the assignment which minimizes this cost.
The plot shows this value step by step. The two ways exhibit really different behaviors. Computing communities directly shows a strong instability: a minor transformation of the network (removing one node) leads to major modifications of the partitions. On the other hand, the partitions obtained with a using the previous communities are extremely stable except at a few pikes which may correspond to events on the network, like deleting a node of high degree or splitting in two big connected components.