Community Detection in Large-Scale Social Networks: A Survey

2. Communities In Social Networks

Community in a social network is a group of nodes that are densely connected and sparsely connected with the rest of the network. It is also defined as collection of nodes with high density of internal links and with low density of external links. A community can also be called as module, cluster or group. Community detection has importance over several disciplines such as biology, statistical physics, sociology, applied mathematics and computer science. Communities are broadly classified into two categories based on node participation. One is disjoint community, where a node can be a member of only one community at most. The other is overlapping community, where a node can be a member of more than one community. In the real world networks, several overlapping communities can exists. For example, in social networks, a person may be a member of family circle, job circle and friend circle at the same time. Hence, the study of overlapping communities is the most relevant concept in real world social networks. The illustration of disjoint and overlapping communities in a sample network is depicted in Figure 1 and Figure 2 respectively.

Figure 1.

Example for disjoint communities

Figure 2.

Example for overlapping communities

In Figure 1, a sample network with two disjoint communities is depicted (each color represents one community). In Figure 2, a sample network with two overlapping communities is depicted and node 5 is participated in both the communities, hence it is called as overlapping node.