Skip to main content
Article
Community Search in a Multi-Attributed Graph using Collaborative Similarity Measure and Node Filtering
Proceedings of the 2021 15th International Conference on Ubiquitous Information Management and Communication, IMCOM 2021
  • Naveed Javaid, National University of Computer Emerging Sciences
  • Kifayat Ullah Khan, National University of Computer Emerging Sciences
  • Asad Masood Khattak, Zayed University
  • Waqas Nawaz, Islamic University of Madinah
Document Type
Conference Proceeding
Publication Date
1-4-2021
Abstract

Community search is a well studied problem in literature to find similar and strongly connected vertices in a graph for a give set of query vertices. It can assist in finding similar structures in a large graph and has many potential applications in different domains, such as molecular biology, data science, and sociology. However, it is non-trivial to identify analogous communities in a large multi-attributed graph for a given query graph due to complex structure of underlying network. Majority of the existing approaches either focus on structural or attributed aspect of the network for community search in a multi-attributed graph, while other are computation intensive. Therefore, we introduce a simple and efficient approach to find communities for a given query graph using collaborative similarity measure (CSM) and representation selection strategy. We apply an incremental clustering approach to determine k sets of nodes from the original graph based on structural and attribute similarity. Afterwards, we find representative and most relevant vertices in each cluster using PageRank approach. In order to get optimal communities, we perform clustering coefficient based pruning on the resultant communities. The experimental analysis on various real-world graphs shows the effectiveness and efficiency of our approach in terms of execution time and results accuracy.

ISBN
9780738105086
Publisher
IEEE
Keywords
  • Collaborative Similarity Measure,
  • Community Search,
  • Multi-Attributed Graph,
  • Representative Selection
Scopus ID
85103739960
Indexed in Scopus
Yes
Open Access
No
https://doi.org/10.1109/IMCOM51814.2021.9377423
Citation Information
Naveed Javaid, Kifayat Ullah Khan, Asad Masood Khattak and Waqas Nawaz. "Community Search in a Multi-Attributed Graph using Collaborative Similarity Measure and Node Filtering" Proceedings of the 2021 15th International Conference on Ubiquitous Information Management and Communication, IMCOM 2021 (2021)
Available at: http://works.bepress.com/asad-khattak/26/