Community Detection in Large-Scale Social Networks: A Survey

Community Detection in Large-Scale Social Networks: A Survey

S Rao Chintalapudi (Jawaharlal Nehru Technological University, Kakinada (JNTU-K), India) and M. H. M. Krishna Prasad (Jawaharlal Nehru Technological University, Kakinada (JNTU-K), India)
DOI: 10.4018/978-1-5225-2814-2.ch012
OnDemand PDF Download:
$30.00
List Price: $37.50

Abstract

Community Structure is one of the most important properties of social networks. Detecting such structures is a challenging problem in the area of social network analysis. Community is a collection of nodes with dense connections than with the rest of the network. It is similar to clustering problem in which intra cluster edge density is more than the inter cluster edge density. Community detection algorithms are of two categories, one is disjoint community detection, in which a node can be a member of only one community at most, and the other is overlapping community detection, in which a node can be a member of more than one community. This chapter reviews the state-of-the-art disjoint and overlapping community detection algorithms. Also, the measures needed to evaluate a disjoint and overlapping community detection algorithms are discussed in detail.
Chapter Preview
Top

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.

Complete Chapter List

Search this Book:
Reset