access icon openaccess Research on semi-supervised community discovery algorithm based on new annealing

This is an open access article published by the IET under the Creative Commons Attribution License (http://creativecommons.org/licenses/by/3.0/)
Received 21/10/2019, Accepted 19/11/2019, Published 13/01/2020

Based on the similarity of the community detection methods, the Givern-Newman (GN) algorithm is fast and accurate but has a higher running time. In order to improve the efficiency of GN Algorithm, this study presents a semi-supervised GN algorithm based on node similarity. By making full use of the constraint set of the prior knowledge must-link and cannot-link, the prior information is extended by the derived rules, and the extended information is verified by the method of distance measurement. Using new annealing maximisation algorithm to calculate node similarity iteratively, and validated using artificial and real networks. It proves that the proposed algorithm reduces the GN algorithm's running time and improves efficiency.

Inspec keywords: complex networks; iterative methods; graph theory; social network theory; network theory (graphs); optimisation

Other keywords: must-link constraints; similarity information; community detection methods; semisupervised GN algorithm; new annealing maximisation algorithm; cannot-link constraints; semisupervised community discovery algorithm; node similarity

Subjects: Interpolation and function approximation (numerical analysis); Combinatorial mathematics; Systems theory applications in social science and politics; Optimisation techniques

References

    1. 1)
      • 1. Xu, W., Yu, J.: ‘A novel approach to information fusion in multi-source datasets: a granular computing viewpoint’, Inf. Sci., 2017, 378, pp. 410–423.
    2. 2)
      • 25. Raghavan, U.N., Albert, R., Kumara, S.: ‘Near linear time algorithm to detect community structures in large-scale networks’, Phys. Rev. E, 2007, 76, p. 036106.
    3. 3)
      • 26. Sun, P.G., Gao, L., Shan Han, S.: ‘Identification of overlapping and non-overlapping community structure by fuzzy clustering in complex networks’, Inf. Sci., 2011, 181, (6), pp. 1060–1071.
    4. 4)
      • 6. Xu, W., Li, M., Wang, X.: ‘Information fusion based on information entropy in fuzzy multi-source incomplete information system’, Int. J. Fuzzy Syst., 2017, 19, (4), pp. 1200–1216.
    5. 5)
      • 4. Xu, W., Guo, Y.: ‘Generalized multigranulation double-quantitative decision-theoretic rough set’, Knowl.-Based Syst., 2016, 105, (1), pp. 190–205.
    6. 6)
      • 14. Salton, G.: ‘Automatic text processing: the transformation, analysis, and retrieval of information by computer’ (Addison-Wesley, Academic Press, New York, 1989), pp. 123–145.
    7. 7)
      • 18. Zhang, Z.Y.: ‘Community structure detection in complex networks with partial background information’, Europhys. Lett., 2013, 101, (4), p. 48005.
    8. 8)
      • 12. Ma, X., Gao, L., Yong, X., et al: ‘Semi-supervised clustering algorithm for community detection in complex networks’, Physica A, 2010, 389, (1), pp. 187–197.
    9. 9)
      • 24. Lusseau, D., Schneider, K., Boisseau, O., et al: ‘The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations’, Behav. Ecol. Sociobiol., 2003, 54, (4), pp. 396–405.
    10. 10)
      • 16. Newman, M.E.J.: ‘Modularity and community structure in networks’, Proc. Natl. Acad. Sci., 2006, 103, (23), pp. 8577–8582.
    11. 11)
      • 22. Ng, A.Y., Jordan, M.I., Weiss, Y.: ‘On spectral clustering: analysis and an algorithm’. Proc. Advances in Neural Information Processing Systems, New York, USA, 2001, pp. 849–856.
    12. 12)
      • 19. Zhang, Z.Y., Sun, K.D., Wang, S.Q.: ‘Enhanced community structure detection in complex networks with partial background information’, Sci. Rep., 2013, 3, p. 3241.
    13. 13)
      • 17. Ver Steeg, G., Galstyan, A., Allahverdyan, A.E.: ‘Statistical mechanics of semi-supervised clustering in sparse graphs’, J. Stat. Mech. Theory Exp., 2011, 2011, (8), p. P08009.
    14. 14)
      • 7. Rosvall, M., Bergstrom, C.T.: ‘Maps of random walks on complex networks reveal community structure’, Proc. Natl. Acad. Sci., 2008, 105, (4), pp. 1118–1123.
    15. 15)
      • 8. Sang, B., Guo, Y., Shi, D., et al: ‘Decision-theoretic rough set model of multi-source decision systems’, Int. J. Mach. Learn. Cybern., 2018, 9, pp. 1941–1954.
    16. 16)
      • 11. Liu, Z., Li, P., Zheng, Y., et al: ‘Community detection by affinity propagation’. Technical report, 2008.
    17. 17)
      • 5. Xu, W., Li, W.: ‘Granular computing approach to two-way learning based on formal concept analysis in fuzzy datasets’, IEEE Trans. Cybern., 2016, 46, (2), pp. 366–379.
    18. 18)
      • 9. Chai, B., Wang, J., Yu, J.: ‘A parameter selection method of the deterministic anti-annealing algorithm for network exploring’, Neurocomputing, 2017, 226, pp. 192–199.
    19. 19)
      • 13. Salton, G., Mcgill, M.J.: ‘Introduction to modern information retrieval’ (McGraw-Hill Book Company, Academic Press, New York, 1983), pp. 45–89.
    20. 20)
      • 2. Jiang, Y.: ‘Community detection in complex networks’, Beijing Jiaotong University, Beijing, 2014, pp. 32–33.
    21. 21)
      • 20. Cheng, J., Leng, M., Li, L., et al: ‘Active semi-supervised community detection based on must-link and cannot-link constraints’, PLOS ONE, 2014, 9, (10), pp. 1–18.
    22. 22)
      • 21. Zachary, W.: ‘An information flow model for conflict and fission in small groups’, J. Anthropol. Res., 1977, 33, pp. 452–473.
    23. 23)
      • 15. Hamers, L., Hemeryck, Y., Herweyers, G., et al: ‘Similarity measures in scientometric research: the Jaccard index versus Salton's cosine formula’, Inf. Process. Manage., 1989, 25, (3), pp. 315–318.
    24. 24)
      • 3. Karthik, S., Aggarwal, C.C., Jaideep, S., et al: ‘Community detection with prior knowledge’. SIAM Data Mining, Dalian, Liaoning, China, 2013.
    25. 25)
      • 10. Girvan, M., Newman, M.E.J.: ‘Community structure in social and biological networks’, Proc. Natl. Acad. Sci., 2002, 99, (12), pp. 7821–7826.
    26. 26)
      • 23. Newman, M.E.J.: ‘Fast algorithm for detecting community structure in networks’, Phys. Rev. E, 2004, 69, p. 066133.
http://iet.metastore.ingenta.com/content/journals/10.1049/joe.2019.1186
Loading

Related content

content/journals/10.1049/joe.2019.1186
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading