Community discovery in complex networks is an interesting problem with a number of applications, especially in the knowledge extraction task in social and information networks. However, many large networks often lack a particular community organization at a global level. In these cases, traditional graph partitioning algorithms fail to let the latent knowledge embedded in modular structure emerge, because they impose a top-down global view of a network. We propose here a simple local-first approach to community discovery, able to unveil the modular organization of real complex networks. This is achieved by democratically letting each node vote for the communities it sees surrounding it in its limited view of the global system, i.e. its ego neighborhood, using a label propagation algorithm; finally, the local communities are merged into a global collection. We tested this intuition against the state-of-the-art overlapping and non-overlapping community discovery methods, and found that our new method clearly outperforms the others in the quality of the obtained communities, evaluated by using the extracted communities to predict the metadata about the nodes of several real world networks. We also show how our method is deterministic, fully incremental, and has a limited time complexity, so that it can be used on web-scale real networks.
There has been a quickly growing interest in networks, since they can represent the structure of a wide class of complex systems occurring from the level of cells to society. Data obtained on real networks show that the corresponding graphs exhibit unexpected nontrivial properties, e.g., anomalous degree distributions, diameter, spreading phenomena, clustering coefficient, and correlations [1]. Very recently great attention has been paid to the local structural units of networks. Small and well defined subgraphs have been introduced as ‘‘motifs’’ [2]. Their distribution and clustering properties [2,3] can be used to interpret global features as well. Somewhat larger units, made up of vertices that are more densely connected to each other than to the rest of the network, are often referred to as communities [4], and have been considered to be the essential structural units of real networks. They have no obvious definition, and most of the recent methods for their identification rely on dividing the network into smaller pieces. The biggest drawback of these methods is that they do not allow for overlapping communities, although overlaps are generally assumed to be crucial features of communities. In this Letter we lay down the fundamentals of a kind of percolation phenomenon on graphs, which can also be used as an effective and deterministic method for uniquely identifying overlapping communities in large real networks [5]. Meanwhile, the various aspects of the classical Erdo ýs Network theory has become pervasive in all sectors of biology, from biochemical signalling to human societies, but identification of relevant functional communities has been impaired by many nodes belonging to several overlapping groups at once, and by hierarchical structures. These authors offer a radically different viewpoint, focusing on links rather than nodes, which allows them to demonstrate that overlapping communities and network hierarchies are two faces of the same issue. 