A Method To Improve The Time Of Computing For Detecting Community Structure In Social Network Graph
Nguyen Xuan Dung1, Doan Van Ban2, Truong Tien Tung3
1Nguyen Xuan Dung*, Hanoi Open University, Hanoi, Vietnam.
2Doan Van Ban, Vietnam Academy of Science and Technology, Hanoi, Vietnam.
3Truong Tien Tung, Hanoi Open University, Hanoi, Vietnam.
Manuscript received on July 20, 2019. | Revised Manuscript received on August 10, 2019. | Manuscript published on August 30, 2019. | PP: 933-937 | Volume-8 Issue-6, August 2019. | Retrieval Number: F8235088619/2019©BEIESP| DOI: 10.35940/ijeat.F8235.088619
Open Access | Ethics and Policies | Cite | Mendeley
© The Authors. Blue Eyes Intelligence Engineering and Sciences Publication (BEIESP). This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/)
Abstract: Identifying communities has always been a fundamental task in analysis of complex networks. Currently used algorithms that identify the community structures in large-scale real-world networks require a priori information such as the number and sizes of communities or are computationally expensive. Amongst them, the label propagation algorithm (LPA) brings great scaslability together with high accuracy but which is not accurate enough because of its randomness. In this paper, we study the equivalence properties of nodes on social network graphs according to the labeling criteria to shorten social network graphs and develop label propagation algorithms on shortened graphs to discover effective social networking communities without requiring optimization of the objective function as well as advanced information about communities. Test results on sample data sets show that the proposed algorithm execution time is significantly reduced compared to the published algorithms. The proposed algorithm takes an almost linear time and improves the overall quality of the identified community in complex networks with a clear community structure.
Keywords: Class of equivalent nodes, community structure, identical nodes, label propagation.