An Algorithm of Inductively Identifying Clusters from Attributed Graphs

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

Research output: Contribution to journalArticlepeer-review

8 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 identify 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 cooccur 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 also able to classify clusters such that their significances can be indicated. The experimental results demonstrate the performance and usefulness of our algorithm.

Original languageEnglish (US)
JournalIEEE Transactions on Big Data
DOIs
StateAccepted/In press - 2020

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Information Systems and Management

Keywords

  • Attributed graph
  • Big Data
  • Clustering algorithms
  • Portfolios
  • Signal processing algorithms
  • Social networking (online)
  • Task analysis
  • Weight measurement
  • 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