Determining maximum cliques for community detection in weighted sparse networks

摘要

In this article, we have delved into detecting dense regions of weighted sparse networks through identification of cliques and communities. A novel clique finding method is introduced to generate all maximum cliques of a sparse network, with focus on analysis of real-life networks and a community detection algorithm is devised on maximal cliques to determine possible overlapping communities of the weighted sparse network. A good number of methods of clique detection already exist, some of which are truly efficient, but many of them lack direct applicability to real-life network analysis, as they deal with simple networks, hide intermediary details and allow cliques to be formed without information on strength of interactions in group behavior. The proposed method attaches a clique-intensity value with every clique and using two thresholds on intensity of interactions, at the individual level and group level, provides handle to filter stray or insignificant interactions at various stages of clique formation. Using differently sized weighted maximal cliques as building blocks, a new overlapping community detection method is proposed using a new measure, a weighted version of Jaccard index, called weighted Jaccard index. Experiments are done on real-life networks; the maximum clique structures reveal sensitivity to threshold values, while the resulting community structures demonstrate efficacy of the community detection method.