Community Tracking in Evolving Social Networks

A social network is a social structure of people related to each other through a common relationship or interest, and the process of investigating it through network and graph theories is called social network analysis. In the last decade, modeling and mining social networks have attracted more and more attention, many researchers are seeking to reveal hidden patterns and their evolutions which can capture interactions between people and groups of people, as well as the associated resources for understanding their behavior. In our research, we focused on finding and analyzing the evolution of communities in dynamic social networks, which is also known as tracking communities over time. To achieve this, a community-matching strategy is devised, each evolving community will be characterized by a series of significant evolutionary communities. In the social network analysis area, most of the authors just focus on detecting changes (critical events like form, expand, merge, split, etc.) communities may undergo. And they evaluate their algorithms by looking at the number of occurrences of critical events during the whole time period, barely focus on tracking community itself. Several methods for tracking communities have been proposed, most of which use however a sequential approach to perform one-to-one community mapping, and the communities are compared in terms of shared-nodes (mostly used Jaccard Coefficient based similarity measure) at only consecutive timestamps. Such one-sided approaches could lead us to a wrong direction of tracking which neglects the social positions of community members and decreases the possibilities of finding the maximum potential evolutions. To alleviate the limitations mentioned above, we propose a new algorithm for tracking communities. We adopted a two-stage process as follows: first independently detecting communities at each snapshot, then performing many-to-many communitymatching on the whole time period with a novel similarity measure to generate a sequence to represent the evolution. The similarity measure we proposed is capable of not only capturing shared-nodes proportion numerically (content similarity), but also the importance of their common members (member quality), and time proximity between communities when we match them. For the tracking strategy, we maximize the pair-wise similarity over all selected matches, which allows for many-to-many mappings between communities across different time steps. The matching is implemented over the entire observation period. It means our method will be able to maximize the potential evolutions we could find. To demonstrate the capacity of the proposed approach to increase the accuracy of tracking, we performed experimental studies. We carried a comparative study between four existing approaches and our proposed approach for tracking communities to clarify their strength and weakness. In our analysis, we compare the algorithms separately in two main community sets: (1) when groups of users do not…