Community Structure Extraction for Social Networks

Community Structure Extraction for Social Networks

Helen Hadush (North Carolina Central University, USA), Gaolin Zheng (North Carolina Central University, USA), Chung-Hao Chen (North Carolina Central University, USA) and E-Wen Huang (National Central University, Taiwan)
DOI: 10.4018/978-1-61350-444-4.ch015
OnDemand PDF Download:
No Current Special Offers


In this work, community structure extraction essentially resorts to its solution to graph partition problem. The authors explore two different approaches. The spectral approach is based on the minimization of balanced cut and its resulting solution comes from the spectral decomposition of the graph Laplacian. The modularity based approach is based on the maximization of modularity and implemented in a hierarchical fashion. In practice, the approach can extract useful information from the community structure, such as what is the most influential component in a given community. Being able to identify and group friends on social networks, the technique can provide a customized advertisement based on their interests. This can have a big return in terms of marketing efficiency. Community structure can also be used for network visualization and navigation. As a result, it can be seen which groups or which pages have more interaction, thus giving a clear image for navigation purposes.
Chapter Preview


The word “community” is a broad term for fellowship or organized society. Society offers a wide variety of possible group organizations: families, workspace and friendship circles, villages, towns, nations. The popularization of Internet has also led to the creation of virtual groups such as online communities. Indeed, social communities have been studied for a long time (Freeman 2004). Communities also occur in many networked systems from biology, computer science, engineering, economics, politics, etc. For example, in protein-protein interaction networks, communities are likely to group proteins of similar functions within the cell (Rives and Galitski 2003), in the World Wide Web they may correspond to groups of pages dealing with the same or related topics (Dourisboure, Geraci et al. 2007), in metabolic networks they may be related to functional modules such as cycles and pathways (Guimera and Nunes Amaral 2005), in food webs they may identify layers, and so on.

Communities can also have real applications. For example clustering web clients who have similar interests and are geographically close to each other may improve the performance of services provided on the World Wide Web, in that each cluster of clients could be served by a dedicated mirror server (Krishnamurthy and Wang 2000). Identifying clusters of customers with similar interests in the network of purchase relationships between customers and products of online retailers (e.g., enables us to set up efficient recommendation systems (Reddy, Kitsuregawa et al. 2002). Such a system increases the business opportunity by directing customers better through the list of items of the retailer. Clustering of large graphs can be used to create data structures for efficient storage and navigational queries, like path searches(Agrawal and Jagadish 1994). Graphs are used to represent networks due to their very relevant feature, namely community structure. The organization of vertices in clusters is in such a way that edges joining vertices of the same cluster or community appear higher in number than the edges joining vertices of different clusters. Figure 1 illustrates this property. Grouping the nodes into clusters enables one to generate compact routing tables while the choice of the communication paths is still efficient (Steenstrup 2001).

Figure 1.

Three communities, denoted by the dashed circles, which have dense intra-community links and sparse inter-community links


In addition, community identification is useful for many more important reasons. Identifying clusters and their boundaries allows for a classification of vertices, according to their structural position in the clusters. Vertices with a central position in their clusters, i.e. sharing relatively many edges with the other group members, may have a key role of control and stability within the group; vertices lying at the boundaries between clusters play a key role of intercession and guide the relationships and exchanges between different communities(Csermely 2008). Finally, we can study the graph where vertices are the communities and edges are put between clusters if there are connections between some of their vertices in the original graph. As a result we can attain a clear description of the original graph, which reveals the relationships between clusters. Recent studies indicate that networks of communities have a different degree distribution with respect to the full graphs(Palla, Derenyi et al. 2005).

Complete Chapter List

Search this Book: