Background: The detection of communities within complex networks is a nontrivial problem, due mainly to the intricacy of how edges should be processed within a network. The detection problem is compounded by individual members naturally occurring in more than one community. Many of the current approaches have constrained a member to be in only one community; this limitation can significantly impact the results of community detection algorithms. Additionally, a common practice in community detection is to view the network as a whole and have a central control process determine where and how nodes are clustered. Viewing the network as a whole introduces resolution problems since a given community cluster could erroneously influence how non-neighboring clusters are detected. Central control can pose a limitation on how communities are detected and impact performance.;Objective: Finding overlapping communities, ones that allow a member to be in more than one community, is an important step into being able to understand and analyze complex networks. This work proposes an approach to overlapping community detection that operates by finding communities based on each vertex's local view. Each vertex intrinsically knows its community membership through its local structure. That knowledge can be aggregated to uncover the naturally occurring overlapping communities.;Method: This work introduces the notion of ego-based overlapping community detection that operates in a two-step approach. The first step is the identification of the local communities associated with each vertex. This local community is called the egonet. The second step merges other nearby local communities, within a parameterized similarity threshold, into larger communities. Once no additional mergers can occur, the result is the detection of the global overlapping community structure.;Results: This work includes two ego-based overlapping community detection implementations. The first is a brute force implementation that merges ego-community sets based on an overlap similarity score. Merging is handled through a traditional union of sets. The second implementation replaces the merge process with a label propagation scheme that uses the local structure of the network to manage how the network is processed. By extracting structural information from the local network, the ego-communities extracted from egonets, propagation and merging of communities can be controlled. Both implementations were written in Java and are available on GitHub1.;Conclusion: The result is a fast and flexible approach that detects overlapping communities that runs in O(n log2 n) time.;1 https://github.com/Rees-Brad/FastEgoClustering.
展开▼
