Adapting the TopLeaders algorithm for dynamic social networks
- PDF / 2,856,226 Bytes
- 23 Pages / 439.37 x 666.142 pts Page_size
- 50 Downloads / 168 Views
Adapting the TopLeaders algorithm for dynamic social networks Wenhao Gao1 · Wenjian Luo1 · Chenyang Bu1
© Springer Science+Business Media New York 2017
Abstract Evolutionary community discovery is a hot research topic related to the dynamic or temporal social networks. The communities detected in a dynamic network should get reasonable partition for the current network and do not deviate drastically from the previous ones. This paper is an extended version of our previous work in Gao et al. (in: Proceedings of the 2016 international conference on big data and smart computing (BigComp), pp 53–60, 2016). First, an evolutionary community discovery algorithm named EvoLeaders, which is inspired by TopLeaders algorithm, is proposed. Second, based on TopLeaders, an improved TopLeaders algorithm (i.e., AutoLeaders) is proposed. Experiments on three classic data sets are conducted, and experimental results show that the AutoLeaders can correctly find the number of communities and at the same time can discover reasonable communities. Third, the EvoAutoLeaders algorithm is proposed for detecting the communities in a dynamic network. Compared with the TopLeaders algorithm and EvoLeaders, experimental results over two real-world data sets demonstrate that the EvoAutoLeaders is more suitable for dynamic scenarios. Keywords Dynamic social network · Community discovery · Leader nodes
This paper is recommended by the BigComp 2016 conference as one of the selected papers.
B
Wenjian Luo [email protected] Wenhao Gao [email protected] Chenyang Bu [email protected]
1
Anhui Province Key Laboratory of Software Engineering in Computing and Communication, School of Computer Science and Technology, University of Science and Technology of China, Hefei 230027, Anhui, China
123
W. Gao et al.
1 Introduction A social network is a graph of relationships between individuals, where each edge represents the interaction between two individuals (e.g., emails communication, cell phones communication and hyperlinks in blogs). One of the most important problems in social networks is the detection of communities. Within a community, the connections are dense, while the connections between different communities are sparse [2–6]. Traditional approaches to analyze social network treat the network as a static graph, which aggregates interactions over all the time into one snapshot. However, in many real-world networks, the relationships between individuals may evolve over time. Omitting the temporal information in the networks, some valuable communities could not be able to be found and the temporal evolution of the communities could not be detected. Recently, there are a growing number of literatures about the community discovery and temporal evolution in dynamic networks [7–17]. A common model for such temporal or dynamic networks is using a series of consecutive snapshots of the graph, where each snapshot corresponds to a time step. By considering the current snapshot together with the recent past snapshots, such a model is often u
Data Loading...
