Robustness in network community detection under links weights uncertainties

• Approach for analyzing the effect of uncertainties in the link weights of a network as a function of network similarity.
• Global similarity between the original and the perturbed partitions of networks is evaluated.
• Robustness of all of the original communities is quantified.
• Robustness of all of the original inter-community links (ICL) is identified.
• Use of a confidence level allows qualifying the communities or the ICL as robust.

In network analysis, a community can be defined as a group of nodes of a network (or clusters) that are densely interconnected with each other but only sparsely connected with the rest of the network. Several algorithms have been used to obtain a convenient partition allowing extracting the communities in a given network, based on their topology and, possibly, the weights of links. These weights usually represent specific characteristics for example: distance, reactance, reliability. Even if the optimum partitions could be derived, there are uncertainties associated to the network parameters that affect the network partition. In this paper, the authors extend a previous approach for assessing the effects of weight uncertainties on community structures and propose a global approach for (a) understanding the global similarity among the partitions; (b) analyzing the robustness of the communities derived without uncertainty; and (c) quantifying the robustness of the inter-community links. To this aim an uncertainty propagation analysis, based on the Monte Carlo technique is proposed. The approach is illustrated through analyzing the topology of an electric power system.