Detecting Communities in Dynamic Social Networks using Modularity Ensembles SOM

Introduction

Social network analysis has gained much attention. Social network analysis is emerging as one of the most important research domains by which useful information from social network data can be extracted. Social networks, such as Twitter, Bebo and Facebook, are growing rapidly in recent years. A social network is a combination of set of nodes and edges. The edges are used to connect nodes in various relationships such as friendship, kinship, etc. Social networks have been known to contain many different properties such as small world effect (i.e., the node to node distance is extremely small even though they show high local cohesion), power law degree distribution (the distribution of number of neighbors of a node, called its degree, is often heterogeneous) and network transitivity (Boccaletti, Latora, Moreno, Chavez, & Hwang, 2006) etc. Apart from these, many social networks also contain the property of community structure (Girvan & Newman, 2002; Palla, Pollner, Barabasi, & Vicsek, 2009), i.e., their vertices are naturally divided into different denser groups having more links or connections inside each group and fewer links between groups.

A social network can be modeled as a graph, where nodes or vertices represent users of the social network and links or edges represent social interactions and affiliations with other users. The members present in each community of a social network share things in common such as interests in music, movies, photography, common hobbies or common discussion topics which may probably make them to interact more frequently with each other than with the members present in other communities. Figure 1 shows a diagram of a social network with community structure.

Figure 1.

A schematic diagram showing a social network with three community structures. (Drawn using social network visualization tool Gephi)

However, social networks of real time are not always static. In fact, in reality almost all social networks (such as Twitter, Bebo and Facebook) are dynamic and evolve with time, expand in size as their users are increased, thus they themselves add to the area of dynamic networks. A dynamic network is one in which changes are introduced frequently over time. In case of online social networks such as Twitter, Facebook or Flickr, changes are usually introduced by users joining in or withdrawing from one or more groups or communities; by connecting friend’s friends and by making new friends with other people. In general, a dynamic social network is represented as a sequence of snapshots of graphs. Thus, it is important to consider the temporal aspect of the network because these networks keep changing. In real-world social network analysis problems, modeling structural changes in networks is important and has a wide range of applications such as the analysis of mobile subscriber networks (Wu, Ye, & Yang, 2009), the analysis of the evolution of research communities within and across academic disciplines (Palla et al., 2007), worm containment in dynamic networks. The communities, when detected, reveal interrelationship, associations, and behavioral trends among the members (Ting, 2008). For example, the research community, when detected, in a social network may reveal domain specific Special Interest Groups (SIGs) which will be further used for effective research interactions among the members.

In this paper, a novel method, called community detection using modularity ensembled with self-organizing maps (SOM), is devised to detect the number of communities in dynamic social networks. The work becomes important considering the fact that knowledge discovery from such social networks is a buzz activity and has broad range of applications.