Detecting Communities and Correlated Attribute Clusters on Multi-Attributed Graphs

Hiroyoshi ITO; Takahiro KOMAMIZU; Toshiyuki AMAGASA; Hiroyuki KITAGAWA

doi:10.1587/transinf.2018DAP0022

Detecting Communities and Correlated Attribute Clusters on Multi-Attributed Graphs

Hiroyoshi ITO, Takahiro KOMAMIZU, Toshiyuki AMAGASA, Hiroyuki KITAGAWA

Full Text Views

0

Cite this

Summary :

Multi-attributed graphs, in which each node is characterized by multiple types of attributes, are ubiquitous in the real world. Detection and characterization of communities of nodes could have a significant impact on various applications. Although previous studies have attempted to tackle this task, it is still challenging due to difficulties in the integration of graph structures with multiple attributes and the presence of noises in the graphs. Therefore, in this study, we have focused on clusters of attribute values and strong correlations between communities and attribute-value clusters. The graph clustering methodology adopted in the proposed study involves Community detection, Attribute-value clustering, and deriving Relationships between communities and attribute-value clusters (CAR for short). Based on these concepts, the proposed multi-attributed graph clustering is modeled as CAR-clustering. To achieve CAR-clustering, a novel algorithm named CARNMF is developed based on non-negative matrix factorization (NMF) that can detect CAR in a cooperative manner. Results obtained from experiments using real-world datasets show that the CARNMF can detect communities and attribute-value clusters more accurately than existing comparable methods. Furthermore, clustering results obtained using the CARNMF indicate that CARNMF can successfully detect informative communities with meaningful semantic descriptions through correlations between communities and attribute-value clusters.

Publication: IEICE TRANSACTIONS on Information Vol.E102-D No.4 pp.810-820

Publication Date: 2019/04/01

Publicized: 2019/02/04

Online ISSN: 1745-1361

DOI: 10.1587/transinf.2018DAP0022

Type of Manuscript: Special Section PAPER (Special Section on Data Engineering and Information Management)

Category

Authors

Hiroyoshi ITO
  University of Tsukuba
Takahiro KOMAMIZU
  Nagoya University
Toshiyuki AMAGASA
  University of Tsukuba
Hiroyuki KITAGAWA
  University of Tsukuba

Keyword

clustering, community detection, non-negative matrix factorization

Cite this

Copy

Hiroyoshi ITO, Takahiro KOMAMIZU, Toshiyuki AMAGASA, Hiroyuki KITAGAWA, "Detecting Communities and Correlated Attribute Clusters on Multi-Attributed Graphs" in IEICE TRANSACTIONS on Information, vol. E102-D, no. 4, pp. 810-820, April 2019, doi: 10.1587/transinf.2018DAP0022.
Abstract: Multi-attributed graphs, in which each node is characterized by multiple types of attributes, are ubiquitous in the real world. Detection and characterization of communities of nodes could have a significant impact on various applications. Although previous studies have attempted to tackle this task, it is still challenging due to difficulties in the integration of graph structures with multiple attributes and the presence of noises in the graphs. Therefore, in this study, we have focused on clusters of attribute values and strong correlations between communities and attribute-value clusters. The graph clustering methodology adopted in the proposed study involves Community detection, Attribute-value clustering, and deriving Relationships between communities and attribute-value clusters (CAR for short). Based on these concepts, the proposed multi-attributed graph clustering is modeled as CAR-clustering. To achieve CAR-clustering, a novel algorithm named CARNMF is developed based on non-negative matrix factorization (NMF) that can detect CAR in a cooperative manner. Results obtained from experiments using real-world datasets show that the CARNMF can detect communities and attribute-value clusters more accurately than existing comparable methods. Furthermore, clustering results obtained using the CARNMF indicate that CARNMF can successfully detect informative communities with meaningful semantic descriptions through correlations between communities and attribute-value clusters.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2018DAP0022/_p

Copy

@ARTICLE{e102-d_4_810,
author={Hiroyoshi ITO, Takahiro KOMAMIZU, Toshiyuki AMAGASA, Hiroyuki KITAGAWA, },
journal={IEICE TRANSACTIONS on Information},
title={Detecting Communities and Correlated Attribute Clusters on Multi-Attributed Graphs},
year={2019},
volume={E102-D},
number={4},
pages={810-820},
abstract={Multi-attributed graphs, in which each node is characterized by multiple types of attributes, are ubiquitous in the real world. Detection and characterization of communities of nodes could have a significant impact on various applications. Although previous studies have attempted to tackle this task, it is still challenging due to difficulties in the integration of graph structures with multiple attributes and the presence of noises in the graphs. Therefore, in this study, we have focused on clusters of attribute values and strong correlations between communities and attribute-value clusters. The graph clustering methodology adopted in the proposed study involves Community detection, Attribute-value clustering, and deriving Relationships between communities and attribute-value clusters (CAR for short). Based on these concepts, the proposed multi-attributed graph clustering is modeled as CAR-clustering. To achieve CAR-clustering, a novel algorithm named CARNMF is developed based on non-negative matrix factorization (NMF) that can detect CAR in a cooperative manner. Results obtained from experiments using real-world datasets show that the CARNMF can detect communities and attribute-value clusters more accurately than existing comparable methods. Furthermore, clustering results obtained using the CARNMF indicate that CARNMF can successfully detect informative communities with meaningful semantic descriptions through correlations between communities and attribute-value clusters.},
keywords={},
doi={10.1587/transinf.2018DAP0022},
ISSN={1745-1361},
month={April},}

Copy

TY - JOUR
TI - Detecting Communities and Correlated Attribute Clusters on Multi-Attributed Graphs
T2 - IEICE TRANSACTIONS on Information
SP - 810
EP - 820
AU - Hiroyoshi ITO
AU - Takahiro KOMAMIZU
AU - Toshiyuki AMAGASA
AU - Hiroyuki KITAGAWA
PY - 2019
DO - 10.1587/transinf.2018DAP0022
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E102-D
IS - 4
JA - IEICE TRANSACTIONS on Information
Y1 - April 2019
AB - Multi-attributed graphs, in which each node is characterized by multiple types of attributes, are ubiquitous in the real world. Detection and characterization of communities of nodes could have a significant impact on various applications. Although previous studies have attempted to tackle this task, it is still challenging due to difficulties in the integration of graph structures with multiple attributes and the presence of noises in the graphs. Therefore, in this study, we have focused on clusters of attribute values and strong correlations between communities and attribute-value clusters. The graph clustering methodology adopted in the proposed study involves Community detection, Attribute-value clustering, and deriving Relationships between communities and attribute-value clusters (CAR for short). Based on these concepts, the proposed multi-attributed graph clustering is modeled as CAR-clustering. To achieve CAR-clustering, a novel algorithm named CARNMF is developed based on non-negative matrix factorization (NMF) that can detect CAR in a cooperative manner. Results obtained from experiments using real-world datasets show that the CARNMF can detect communities and attribute-value clusters more accurately than existing comparable methods. Furthermore, clustering results obtained using the CARNMF indicate that CARNMF can successfully detect informative communities with meaningful semantic descriptions through correlations between communities and attribute-value clusters.
ER -