Username   Password       Forgot your password?  Forgot your username? 


An Improved Algorithm based on Time Domain Network Evolution

Volume 14, Number 5, May 2018, pp. 1004-1013
DOI: 10.23940/ijpe.18.05.p19.10041013

Guanghui Yana, Qingqing Maa, Yafei Wanga, Yu Wua, and Dan Jinb

aSchool of Electronic and Information Engineering, Lanzhou Jiaotong University, Lanzhou, 730070, China
bGansu Electric Power Information Communication Centre, Lanzhou, 730070, China

(Submitted on January 18, 2018; Revised on March 9, 2018; Accepted on April 21, 2018)


Community evolution is the highlight in the field of complex network. The current typical tracking community algorithms largely focus on adopting the traditional similarity functional measurements to capture the similarity between communities at temporal snapshots. However, it doesn't take into account the actions accumulated with the events and the effects of community members in evolutionary networks. Meanwhile, different communities use traditional tracking methods with a simple similarity function, and as a result, many analogous communities cannot be effectively extracted in the network. To address these shortcomings, in this paper, we propose a much more powerful similarity function to catch and evaluate communities or groups in a successive time frame. We implement a community tracking method in our new function on the basis of previous research, in which we improve accuracy in network structure by taking the diversity corresponding to the active node in network-evolution into consideration. Finally, we find an interesting phenomenon and give a new method to weigh out the relationships involving active nodes within community evolution over time frames. Eventually, the performance of our algorithm is measured by applying it to real datasets and it is tested on tracking community structure and assessing the experimental results that inhibit active nodes extracted from the community. The experimental results show that our algorithm can effectively keep track of community structure and outperform other algorithms.


References: 18

  1.  B. Albert-Laszlo, P. Gergely, T. Vicsek, "Quantifying Social Group Evolution," Nature, vol. 446, no. 7136, pp. 664-671, May 2007
  2. R. Albert, A. L. Barabasi, "Emergence of Scaling in Random Networks," Science, vol. 286, no. 5439, pp. 509-512, October 1999
  3. Z. Anna, G. Bogdan, K. Jarosław, B. Piotr, K. Przemysław, S. Stanisław, "Predicting Community Evolution in Social Networks," Entropy, vol. 17, no. 5, pp. 924-925, May 2015
  4. S. Aral, D. Walker, "Identifying Influential and Susceptible Members of Social Networks," Science, vol. 337, no. 6092, pp. 337-41, July 2012
  5. S. Asur, S. Parthasarathy, D. Ucar, "An Event-based Framework for Characterizing the Evolutionary Behavior of Interaction Graphs," Acm Transactions on Knowledge Discovery from Data, vol. 3, no. 4, pp. 913-921, August 2009
  6. M. Bajec, L. Šubelj, "Robust Network Community Detection using Balanced Propagation," European Physical Journal B, vol. 81, no. 3, pp. 353-362, June 2011
  7. C. Cattuto, L. Gauvin, A. Panisson, "Detecting the Community Structure and Activity Patterns of Temporal Networks: a Non-negative Tensor Factorization Approach," Plos One, vol. 9, no 1, pp.1-13, January 2014
  8. V. Colizza, L. Ferreri, C. Poletto, E. Valdano, "Analytical Computation of the Epidemic Threshold on Temporal Networks," Physical Review X, vol. 18, no. 3, pp. 503-512, April 2015
  9. P. Cunningham, D. Doyle, D. Greene, "Tracking the Evolution of Communities in Dynamic Social Networks," International Conference on Advances in Social Networks Analysis and Mining, pp. 176-183, August 2010
  10. P. Erdos, A. Renyi, "On the Evolution of Random Graphs," Magyar Tud Akad Mat Kutato Int Kozl, vol. 5, pp.17-61, January 1960
  11. J. Fagnan, F. Sangi, M. Takaffoli, O. R. Zaiane, "Tracking Changes in Dynamic Information Networks," Computational Aspects of Social Networks (CASoN), 2011 International Conference on. IEEE, pp. 94-101, October 2011
  12. S. Fortunato, "Community Detection in Graphs," Physics Reports, vol. 486, pp. 75-174, June 2010
  13. M. Girvan, M. E. J. Newman, "Community Structure in Social and Biological Networks," Proceedings of the National Academy of Sciences of the United States of America, vol. 99, no. 12. pp. 7821-7826, April 2002
  14. M. Goldberg, M. Magdonismail, S. Nambirajan, J. Thompson, "Tracking and Predicting Evolution of Social Communities," IEEE Third International Conference on Privacy, vol. 780-783, October 2011
  15. J. Hopcroft, O. Khan, B. Kulis, B. Selman, "Tracking Evolving Communities in Large Linked Networks," Proceedings of the National Academy of Sciences, vol. 1, pp. 5249-53, May 2004
  16. M. Ley, "DBLP: Some Lessons Learned," Proceedings of the vldb endowment, vol. 2, no. 2, pp. 1493-1500, June 2009
  17. G. Rauret, A. Rigol, M. Vidal, "Empirical Analysis of An Evolving Social Network," Science, vol. 311, no. 5757, pp. 88-90, January 2006
  18. S. H. Strogatz, D. J. Watts, "Collective Dynamics of 'Small-world' Networks," Nature, vol. 393, no. 6684, pp. 440-442, March 1998


    Please note : You will need Adobe Acrobat viewer to view the full articles.Get Free Adobe Reader

    Download this file (IJPE-2018-05-19.pdf)IJPE-2018-05-19.pdf[An Improved Algorithm based on Time Domain Network Evolution]666 Kb
    This site uses encryption for transmitting your passwords.