An Algorithm of Inductively Identifying Clusters from Attributed Graphs

Lun Hu, Shicheng Yang, Xin Luo, Meng Chu Zhou

Research output: Contribution to journalArticlepeer-review

12 Scopus citations

Abstract

Attributed graphs are widely used to represent network data where the attribute information of nodes is available. To address the problem of identifying clusters in attributed graphs, most of existing solutions are developed simply based on certain particular assumptions related to the characteristics of clusters of interest. However, it is yet unknown whether such assumed characteristics are consistent with attributed graphs. To overcome this issue, we innovatively introduce an inductive clustering algorithm that tends to address the clustering problem for attributed graphs without any assumption made on the clusters. To do so, we first process the attribute information to obtain pairwise attribute values that significantly frequently co-occur in adjacent nodes as we believe that they have potential ability to represent the characteristics of a given attributed graph. For two adjacent nodes, their likelihood of being grouped in the same cluster can be weighted by their ability to characterize the graph. Then based on these verifed characteristics instead of assumed ones, a depth-first search strategy is applied to perform the clustering task. Moreover, we are able to classify clusters such that their significance can be indicated. The experimental results demonstrate the performance and usefulness of our algorithm.

Original languageEnglish (US)
Pages (from-to)523-534
Number of pages12
JournalIEEE Transactions on Big Data
Volume8
Issue number2
DOIs
StatePublished - Apr 1 2022

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Information Systems and Management

Keywords

  • Attributed graph
  • classification
  • clustering

Fingerprint

Dive into the research topics of 'An Algorithm of Inductively Identifying Clusters from Attributed Graphs'. Together they form a unique fingerprint.

Cite this