Article Preview
TopIntroduction
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.