Global Community Extraction in Social Network Analysis

Introduction

Social network analysis has been focused by great many researchers. The community structure, containing huge information of the network, is one of the most important directions in social network analysis.

A social network is usually organized as a graph. A vertex indicates a person in the network, and edges present the relation between persons. Therefore, communities in social networks are groups of vertices which probably share common properties. As another popular definition, communities can also be a dense sub-graph, that is, edges between vertices in the sub-graph are much more than those between vertices in and out of the sub-graph. Figure 1 shows a schematic example of a graph with three communities.

Figure 1.

A simple graph with three communities, enclosed by the gray circles

In order to extract the whole structure of the network, researchers propose the global community extraction methods, in which each vertex of the input graph is assigned to a community in the output of the method. There are mainly three kinds of methods at present to extract global communities: divisive algorithms, modularity-based algorithms, and dense sub-graph algorithms.

Divisive clustering algorithms are a class of hierarchical methods that work top-down, recursively partitioning the graph into clusters (communities), during which the split is typically into two sets. Modularity-based algorithms are to optimize the modularity criterion, defined by Newman and Girvan (Newman, 2004a). For dense sub-graph algorithms, they extract the dense regions in the graph to indicate the whole network structure, which is already acceptable.

In this chapter, we will detailed describe the global community extraction methods. Firstly, the background for global community extraction is presented. Section 1 discusses divisive algorithms, such as, related works and potential problems. Then modularity-based algorithms and dense sub-graph algorithms are shown in section 2 and section 3, respectively, followed with conclusion and future work.

Background

As for the huge information, community structure extraction is an essential part in social network analysis. With this structure, we can analyze the group feature of the people more precisely, and then deal with these people, respectively. Plenty of researchers have been conducting research on this direction and done great efforts, for the variety of networks and communities, however, achievement has not been as perfect as we expect.

At the risk of oversimplifying the large and often intricate body of work on community detection in complex networks, the following five-part story describes the general methodology:

• 1.

  Data are modeled by an interaction graph. In particular, part of the world gets mapped to a graph, in which vertices represent entities and edges represent some type of interaction between pairs of those entities.

• 2.

  Hypothesis is made that the world contains groups of entities that interact more strongly amongst themselves than with the outside world.

• 3.

  An algorithm is then selected to find sets of nodes that exactly or approximately optimize this or some other related metric.

• 4.

  The clusters or communities or modules are evaluated in some way.

To extract global community structure, one also needs to choose or design the extracting algorithm to be used within a certain “framework” of defining what global community extraction of a graph is. One decision is that all clusters are independent with each other, namely partition:

The other decision allows for each datum to belong to more than one community, namely overlap or cover.

According to these strategies, a number of algorithms have been put forward in recent years. At the rest of this chapter, some popular global community extraction methods will be discussed.