Global Community Extraction in Social Network Analysis

Global Community Extraction in Social Network Analysis

Xianchao Zhang (Dalian University of Technology, China), Liang Wang (Dalian University of Technology, China), Yueting Li (Dalian University of Technology, China) and Wenxin Liang (Dalian University of Technology, China)
Copyright: © 2013 |Pages: 16
DOI: 10.4018/978-1-4666-2806-9.ch010

Abstract

Great efforts have been made in retrieving the structure of social networks, in which one of the most relevant features is community extraction. A community in social networks presents a group of people focusing on a common topic or interest. Extracting all communities in the whole network, one can easily classify and analyze a specified group of people, which yields amazing results. Global community extraction is due to this demand. In global community extraction (also global clustering), each person of the input network is assigned to a community in the output of the method. This chapter focuses on global community extraction in social network analysis, previous methods proposed by some outstanding researchers, future directions, and so on.
Chapter Preview
Top

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.

Top

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:

(1)

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.

Complete Chapter List

Search this Book:
Reset