Detecting Communities and Correlated Attribute Clusters on Multi-Attributed Graphs
Detecting Communities and Correlated Attribute Clusters on Multi-Attributed Graphs
复制标题
DOI：
10.1587/transinf.2018dap0022
复制
发表时间：
2019-04
期刊：
影响因子：
--
通讯作者：
Hiroyoshi Ito;Takahiro Komamizu;Toshiyuki Amagasa;H. Kitagawa
中科院分区：
文献类型：
--
作者：
Hiroyoshi Ito;Takahiro Komamizu;Toshiyuki Amagasa;H. Kitagawa
摘要多属性图在真实的世界中普遍存在，其中每个节点由多种类型的属性表征。节点社区的检测和表征可能对各种应用产生重大影响。虽然以前的研究已经试图解决这个问题，它仍然是具有挑战性的，由于在集成的图结构与多个属性和噪声的存在下，在图。因此，在这项研究中，我们专注于属性值的集群和社区和属性值集群之间的强相关性。该研究采用的图聚类方法包括社区检测、属性值聚类、社区与属性值聚类之间的关系推导。基于这些概念，提出的多属性图聚类建模为CAR聚类。为了实现CAR聚类，提出了一种基于非负矩阵分解（NMF）的CAR检测算法CARNMF。使用真实数据集进行的实验结果表明，CARNMF方法比现有的同类方法能更准确地检测出社区和属性值聚类。聚类结果表明，CARNMF能够通过社区与属性值聚类之间的相关性，成功地检测出具有语义描述的信息社区。
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 di ffi culties 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 C ommunity detection, A ttribute-value clustering, and deriving R elationships 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. Re-sults 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 re-sults obtained using the CARNMF indicate that CARNMF can successfully detect informative communities with meaningful semantic descriptions through correlations between communities and attribute-value clusters.