On the Detection of Overlapped Network Communities via Weight Redistributions

Abstract

A community is an important attribute of networking, since people who join networks tend to join communities. Community detection is used to identify and understand the structure and organization of real-world networks, thus, it has become a problem of considerable interest. The study of communities is highly related to network partitioning, which is defined as the division of a network into a set of groups of approximately equal sizes with minimum number of edges. Since this is an NP-hard problem, unconventional computation methods have been widely applied. This work addresses the problem of detecting overlapped communities (communities with common nodes) in weighted networks with irregular topologies. These communities are particularly interesting, firstly because they are more realistic, i.e., researchers may belong to more than one research community, and secondly, because they reveal hierarchies of communities: i.e., a medical community is subdivided into groups of certain specialties. Our strategy is based on weight redistribution: each node is examined against all communities and weights are redistributed between the edges. At the end of this process, these weights are compared to the total connectivity of each community, to determine if overlapping exists.