Extending the definition of modularity to directed graphs with overlapping communities

By Vincenzo Nicosia, Giuseppe Mangioni, Vincenza Carchiolo, Michele Malgeri. 2008

460 citations recorded by the source corpus.

Complex network topologies present interesting and surprising properties, such as community structures, which can be exploited to optimize communication, to find new efficient and context-aware routing algorithms or simply to understand the dynamics and meaning of relationships among nodes. Complex networks are gaining more and more importance as a reference model and are a powerful interpretation tool for many different kinds of natural, biological and social networks, where directed relationships and contextual belonging of nodes to many different communities is a matter of fact. This paper starts from the definition of a modularity function, given by Newman to evaluate the goodness of network community decompositions, and extends it to the more general case of directed graphs with overlapping community structures. Interesting properties of the proposed extension are discussed, a method for finding overlapping communities is proposed and results of its application to benchmark case-studies are reported. We also propose a new data set which could be used as a reference benchmark for overlapping community structures identification.

Subfields: Artificial Intelligence, Molecular Biology, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/4ce9de25c6a75938e280915861f9ba812e39d15b

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Molecular Biology

In Statistical and Nonlinear Physics

Citations in the corpus

A classification for community discovery methods in complex networks (2011, background): “Although there are overlapping definitions for this measure [90], the main version used is the standard one which is not defined for overlapping partitions.”
Community detection in social networks (2016, methodology): “A GA for the optimization of modularity, proposed by Nicosia et al.(53), has been explained in the overlapping communities section later.”
Clustering and Community Detection in Directed Networks: A Survey (2013, background): “[73] extended the measure of modularity to the more general case of directed networks with overlapping communities.”
SLPA: Uncovering Overlapping Communities in Social Networks via a Speaker-Listener Interaction Dynamic Process (2011, methodology): “To evaluate the performance of overlapping community detection in real-world networks, we used an overlapping measure, Qov , proposed by Nicosia [19].”
Community detection in graphs (2009, background): “Nicosia et al. (Nicosia et al., 2009) have made some more general considerations on the problem of extending modularity to the case of overlapping communities.”
Towards Linear Time Overlapping Community Detection in Social Networks (2012, methodology): “To quantify the performance, we used the overlapping modularity, Q ov (with values between 0 and 1), proposed by Nicosia [10], which is an extension of Newman’s modularity.”
Finding overlapping communities in networks by label propagation (2009, background): “The overlap modularity measure is deﬁned in terms of a function f , which in turn is deﬁned as but the value of p is not speciﬁed in [22].”
Overlapping community detection in networks: The state-of-the-art and comparative study (2011, background): “Note that a link-based extended modularity is also proposed by Nicosia in [Nicosia et al. 2009].”