Overlapping community search for social networks

Abstract — Finding decompositions of a graph into a family of clusters is crucial to understanding its underlying struc-ture. While most existing approaches focus on partitioning the nodes, real-world datasets suggest the presence of overlapping communities. We present OCA, a novel algorithm to detect overlapped communities in large data graphs. It outperforms previous proposals in terms of execution time, and efficiently handles large graphs containing more than 108 nodes and edges. I. INTRODUCTION AND PRIOR WORK As the importance and use of social networks increases at an ever faster pace, the need to understand and analyze their structure becomes more and more pressing. Given their mod-elization as huge graphs that can contain billions of entities