Community Search in a Multi-Attributed Graph using Collaborative Similarity Measure and Node Filtering

Document Type

Conference Proceeding

Source of Publication

Proceedings of the 2021 15th International Conference on Ubiquitous Information Management and Communication, IMCOM 2021

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

Disciplines

Physical Sciences and Mathematics

Keywords

Collaborative Similarity Measure, Community Search, Multi-Attributed Graph, Representative Selection

Scopus ID

85103739960

Indexed in Scopus

yes

Open Access

no

Link to Full Text

Share

COinS