  The conventional notion of community that favors a high ratio of internal
edges to outbound edges becomes invalid when each vertex participates in
multiple communities. Such a behavior is commonplace in social networks. The
significant overlaps among communities make most existing community detection
algorithms ineffective. The lack of effective and efficient tools resulted in
very few empirical studies on large-scale detection and analyses of overlapping
community structure in real social networks. We developed recently a scalable
and accurate method called the Partial Community Merger Algorithm (PCMA) with
linear complexity and demonstrated its effectiveness by analyzing two online
social networks, Sina Weibo and Friendster, with 79.4 and 65.6 million
vertices, respectively. Here, we report in-depth analyses of the 2.9 million
communities detected by PCMA to uncover their complex overlapping structure.
Each community usually overlaps with a significant number of other communities
and has far more outbound edges than internal edges. Yet, the communities
remain well separated from each other. Most vertices in a community are
multi-membership vertices, and they can be at the core or the peripheral.
Almost half of the entire network can be accounted for by an extremely dense
network of communities, with the communities being the vertices and the
overlaps being the edges. The empirical findings ask for rethinking the notion
of community, especially the boundary of a community. Realizing that it is how
the edges are organized that matters, the f-core is suggested as a suitable
concept for overlapping community in social networks. The results shed new
light on the understanding of overlapping community.
