On the Community Discovery Methods for Complex Networks: A Case Study

• Autorzy: Afrassa Kirubel W. , Cosgun Genco , Gursoy Ulku F. , Yildiz Enes M. , Aktas Mehmet S.

Identyfikatory

DOI

10.15439/2020F88

• Konferencja: Federated Conference on Computer Science and Information Systems (15 ; 06-09.09.2020 ; Sofia, Bulgaria)
• Języki publikacji: EN

Abstrakty

EN

The inherent knowledge discovery problem regarding networks that represent complex real world phenomenon is a popular research topic. Specifically, in social network analysis (SNA), several community discovery techniques with various approaches have been put forward to distinguish closely related entities. Identifying the relevant techniques to utilize based on the context of the application is a key difficulty researchers face. In this study we propose a methodology for classifying these techniques, visualize a prototype, and analyze the performance and quality of selected approaches over a real world call detail record (CDR) data set.

Słowa kluczowe

EN

community discovery; community detection algorithms; visualization; CDR; call detail record

PL

algorytmy detekcji społeczności; wizualizacja; CDR; rejestr połączeń

• Wydawca: Polskie Towarzystwo Informatyczne
• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2020
• Tom: Vol. 21
• Strony: 473--477
• Opis fizyczny: Bibliogr. 36 poz., il., tab., wykr.

Twórcy

autor

Afrassa Kirubel W.

• Computer Engineering Dept., Yildiz Technical University, Istanbul, Turkey

autor

Cosgun Genco

• Computer Engineering Dept., Yildiz Technical University, Istanbul, Turkey

autor

Gursoy Ulku F.

• R&D Center Intellica Business Intelligence Consultancy, Istanbul, Turkey

autor

Yildiz Enes M.

• R&D Center Intellica Business Intelligence Consultancy, Istanbul, Turkey

autor

Aktas Mehmet S.

• Computer Engineering Dept., Yildiz Technical University, Istanbul, Turkey

Bibliografia

• 1. A. Condon and R. M. Karp, “Algorithms for graph partitioning on the planted partition model”, Random Struct Algor 18, pp.116–140, 2001.
• 2. F. Altunbey and B. Alatas, “Overlapping Community Detection in Social Networks Using Parliamentary Optimization Algorithm”, International Journal of Computer Networks and Applications (IJCNA) 2, no. 1, pp. 12–19, 2015.
• 3. N. Du, B. Wu, X. Pei, B. Wang, and L. Xu, “Community detection in large-scale social networks”, The 9th WebKDD and 1st SNA-KDD 2007 workshop on Web mining and social network analysis (WebKDD/SNA-KDD ’07). Association for Computing Machinery, New York, NY, USA, pp. 16-–25, 2007.
• 4. M. S. Khan, A. W. A. Wahab, T. Herawan, G. Mujtaba, S. Danjuma and M. A. Al-Garadi, “Virtual Community Detection Through the Association between Prime Nodes in Online Social Networks and Its Application to Ranking Algorithms”, in IEEE Access, vol. 4, pp. 9614-9624, 2016.
• 5. L. Runpeng, H. Jun and W. Xiaofan, “VCD: A network visualization tool based on community detection”, 2012 12th International Conference on Control, Automation and Systems, JeJu Island, pp. 1221–1226, 2012.
• 6. M. Crampes, M. Plantie, “A unified community detection, visualization and analysis method”, Advances in complex systems, vol. 17, no. 01, pp. 1450001, 2014.
• 7. J. David Cruz, C. Bothorel, and F. Poulet, “Community detection and visualization in social networks: Integrating structural and semantic information”, ACM Trans. Intell. Syst. Technol. 5, 1, Article 11 pp. 26, 2013.
• 8. R. A. Becker, R. Caceres, K. Hanson, J. M. Loh, S. Urbanek, A. Varshavsky, and C. Volinsky, “A tale of one city: Using cellular network data for urban planning”, IEEE Pervasive Computing, 10(4), pp. 18-26, 2011.
• 9. F. Calabrese, L. Ferrari, and V. D. Blondel, “Urban sensing using mobile phone network data: A survey of research”, ACM Comput. Surv., 47(2):25:1–25:20, 2014.
• 10. L. Alexander, S. Jiang, M. Murga, and M. C. Gonz ́alez, “Origin–destination trips by purpose and time of day inferred from mobile phone data”, Transportation Research Part C: Emerging Technologies, 58 pp. 240-–250, 2015.
• 11. O. J ̈arv, R. Ahas, E. Saluveer, B. Derudder, and F. Witlox, “Mobile phones in a traffic flow: a geographical perspective to evening rush hour traffic analysis using call detail records”, PloS one, 7(11) pp. 1–12, 2012.
• 12. A. Bogomolov, B. Lepri, R. Larcher, F. Antonelli, F. Pianesi, and A. Pentland, “Energy consumption prediction using people dynamics derived from cellular network data”, EPJ Data Science, 5(1):13, 2016.
• 13. K. Kim, C. Jun, J. Lee, “Improved churn prediction in telecommunication industry by analyzing a large network”, Expert Systems with Applications, vol. 41, Issue 15, pp. 6575–6584, 2014.
• 14. Baeth, M.J. et al. (2019). Detecting misinformation in social networks using provenance data, CONCURR COMP-PRACT E, 31(3).
• 15. Baeth M. J. et al. (2018) An approach to custom privacy policy violation detection problems using big social provenance data, CONCURR COMP-PRACT E, 30(21).
• 16. Baeth, M.J. et al. (2017). Detecting misinformation in social networks using provenance data, SKG-17.
• 17. Baeth, M.J. et al. (2015). On the Detection of Information Pollution and Violation of Copyrights in the Social Web, SOCA-15.
• 18. Dundar, B. et al. (2016) A Big Data Processing Framework for Self Healing Internet of Things Applications, SKG-16.
• 19. Aktas, M.S. et al. (2019), Provenance aware run-time verification of things for selfhealing Internet of Things applications, CONCURR COMP-PRACT E, http://dx.doi.org/10.1002/cpe.4263.
• 20. Aktaş M.S., (2018) Hybrid cloud computing monitoring software architecture, CONCURR COMP-PRACT E, 30(21).
• 21. Riveni, M. et al. (2019). Application of provenance in social computing: A case study, CONCURR COMP-PRACT E, 31(3).
• 22. Tas, Y. et al. (2016) An Approach to Standalone Provenance Systems for Big Provenance Data, SKG-16.
• 23. Newman, Mark EJ. “The structure and function of complex networks.” SIAM review 45.2, pp. 167–256, 2003.
• 24. C. Michele, F. Giannotti, and D. Pedreschi. “A classification for community discovery methods in complex networks.” Statistical Analysis and Data Mining: The ASA Data Science Journal 4.5, pp. 512-546, 2011.
• 25. R. Milo, S. Shen-Orr, S. Itzkovitz, N. Kashtan, D. Chklovskii, and U. Alon, “Network motifs: simple building blocks of complex networks”, Science, vol. 298, no. 5594, pp. 824—827, October 2002.
• 26. L. Huang, C. Wang, H. Chao, “Higher-Order Multi-Layer Community Detection”, The Thirty-Third AAAI Conference on Artificial Intelligence (AAAI-19), pp. 9945–9946, 2019.
• 27. S. Yu, J. Xu, C. Zhang, F. Xia, Z. Almakhadmeh and A. Tolba, “Motifs in Big Networks: Methods and Applications”, in IEEE Access, vol. 7, pp. 183322–183338, 2019, http://dx.doi.org/10.1109/ACCESS.2019.2960044.
• 28. A. Benson, D. Gleich, and J. Leskovec, “Higher-order organization of complex networks”, Science 353, 6295, pp. 163-–166 2016.
• 29. L. Huang, C. Wang, and H. Chao, “A Harmonic Motif Modularity Approach for Multi-layer Network Community Detection” IEEE International Conference on Data Mining, ICDM, Singapore, November 17-20, pp. 1043-–1048, 2018.
• 30. U. N. Raghavan, R. Albert, and S. Kumara, “Near linear time algorithm to detect community structures in large-scale networks,”, Physical Review E, vol. 76, p. 036106, 2007.
• 31. P. Li, L. Huang, C. Wang, and J. Lai, “EdMot: An Edge Enhancement Approach for Motif-aware Community Detection.”, The 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD ’19), Association for Computing Machinery, New York, NY, USA, pp. 479-–487, 2019, http://dx.doi.org/https://doi.org/10.1145/3292500.3330882
• 32. Stanford Network Analysis Project snap, https://snap.stanford.edu/,Accessed: 2020-05-25
• 33. Dash framework, https://dash.plotly.com/, Accessed: 2020-05-25
• 34. Franz M, Lopes CT, Huck G, Dong Y, Sumer O, Bader GD, “Cytoscape.js: a graph theory library for visualisation and analysis”, Bioinformatics, 32, (2), pp.309–311, 2015
• 35. Jaewon Yang, Jure Leskovec, “Defining and evaluating network communities based on ground-truth”, Knowl. Inf. Syst. 42, 1 (January 2015), 181–213. http://dx.doi.org/https://doi.org/10.1007/s10115-013-0693-z
• 36. B. Rozemberczki, C. Allen and R.Sarkar, “Multi-scale Attributed Node Embedding”, 1909.13021, cs.LG, 2019.

Uwagi

1. This study is supported by TUBITAK TEYDEB under the project ID 3181048.

2. Track 3: Network Systems and Applications

3. Technical Session: Advances in Network Systems and Applications

4. Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2021).