Community Detection Approaches in Real World Networks: A Survey and Classification

Community Detection Approaches in Real World Networks: A Survey and Classification

Pooja Wadhwa (Computer Engineering Department, Netaji Subhas Institute of Technology, New Delhi, India) and M.P.S Bhatia (Computer Engineering Department, Netaji Subhas Institute of Technology, New Delhi, India)
DOI: 10.4018/ijvcsn.2014010103
OnDemand PDF Download:
$30.00
List Price: $37.50

Abstract

Online social networks have been continuously evolving and one of their prominent features is the evolution of communities which can be characterized as a group of people who share a common relationship among themselves. Earlier studies on social network analysis focused on static network structures rather than dynamic processes, however, with the passage of time, the networks have also evolved and the researchers have started to focus on the aspect of studying dynamic behavior of networks. This paper aims to present an overview of community detection approaches graduating from static community detection methods towards the methods to identify dynamic communities in networks. The authors also present a classification of the existing dynamic community detection algorithms along the dimension of studying the evolution as either a two-step approach comprising of community detection via static methods and then applying temporal dynamics or a unified approach which comprises of dynamic detection of communities along with their evolutionary characteristics.
Article Preview

Introduction

In the world of rapidly evolving and emerging technologies, there has been a remarkable growth in online social networks. An online social network is a virtual community consisting of social structures made up of nodes/vertices that represent individuals and links that represent the relationships between them. The network paradigm provides a formal way of representing data and its associations, and forms the basis of any analysis. Today almost anything can be represented in the form of networks. The plethora of different problems, ranging from social interactions to World Wide Web have lead to an interdisciplinary approach to these problems using tools from statistical mechanics, computer science to behavioral sciences and sociology. Social Network Analysis (SNA) (Wasserman & Faust, 1994) is a set of powerful techniques to identify social roles, important groups and hidden structures in organizations and groups. SNA has a long and successful history within sociology; networks are everywhere and related methodology can be used to analyze a wide variety of problems.

Community detection has been an active area of research and has proved to be very useful in understanding behaviour of entities involved in networks. Nodes belonging to a tight-knit community are more likely to have some properties in common. For example in the World Wide Web, community analysis has uncovered thematic clusters, in biochemical networks community detection may result in identification of functional groups. Community detection aims to identify modules and their boundaries which further results in the classification of vertices, according to their structural position in the modules. This further results in identification of the most ‘central’ node in a cluster i.e. the one which shares a large number of edges with the other partners in a group; vertices lying at the boundaries between different clusters act as a ‘bridge’ between different clusters and can be said to lead the relationships and exchanges between different communities.

Another important aspect related to community structure is the hierarchical organization of most of the real world networks. Real networks usually consist of many communities which are in turn composed of many smaller communities each having distinct characteristics. In many real world networks, one may observe that an edge may belong to more than one group. In this case, the problem of community detection leads to the detection of overlapping communities.

The dynamic nature of networks gives rise to evolving communities and a new area of research known as dynamic community detection emerges. We may observe that at a given instance of time a network may have no community structure at all, however, later on one may observe the emergence of a community structure which may mature after some time. So, the study of this dynamism provides an insight into the network evolution with time. Conversation networks like Twitter, Facebook may result in such evolving community networks where one may observe maturing of a community only when a topic propagates to many users and they become inspired or excited and participate in related discussions over a passage of time.

This paper explores the aspect of community detection in online social networks emanating its roots from the traditional methods such as graph partitioning, hierarchical clustering, partitional clustering and the advancements made with time. The aspect of dynamic community detection and the issues related to dynamic community detection will be the focus of the paper. We present a classification of the available research on the basis of the approaches followed in static as well as dynamic community detection which will help users to choose effective techniques for community detection.

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 9: 4 Issues (2017): 2 Released, 2 Forthcoming
Volume 8: 4 Issues (2016)
Volume 7: 4 Issues (2015)
Volume 6: 4 Issues (2014)
Volume 5: 4 Issues (2013)
Volume 4: 4 Issues (2012)
Volume 3: 4 Issues (2011)
Volume 2: 4 Issues (2010)
Volume 1: 4 Issues (2009)
View Complete Journal Contents Listing