Computer Science ›› 2017, Vol. 44 ›› Issue (Z6): 433-437.doi: 10.11896/j.issn.1002-137X.2017.6A.097

Previous Articles     Next Articles

Attributed Graph Clustering Algorithm Based on Cluster-aware Multiagent System

SHI Kai, REN Luo-kun, PENG Yi-ming and LI Hui-jia   

  • Online:2017-12-01 Published:2018-12-01

Abstract: Existing methods to partition nodes into clusters with tight correlations is to apply clustering techniques on attributed graphs based on node connectivity or attribute similarity.In this paper,we comprehend each node as an autonomous agent and developed an accurate multi-agent system to extract overlapping clusters in attributed graphs.First,a kernel function with bandwidth factor is introduced to measure the influence of each agent,and those agents with highest local influence are selected as leader agents.Next,a novel local expansion strategy is proposed,by which each leader agent absorbs the closest followers in the graph.Then,the cluster-aware multiagent system was designed so that the optimal overlapping cluster configuration can be uncovered.Our method is highly efficient,whose computational time nearly linearly depends on the number of edges.Finally,the proposed method is demonstrated on synthetic benchmark graphs and real-life attributed graphs to verify the systematic performance.

Key words: Clustering,Attributed graph,Multiagent cluter-aware system,Centrality,Overlapping nodes

[1] KAUFMAN L,ROUSSEEUW P J.Finding groups in data.an introduction to cluster analysis[J/OL].http://library.mpibberlin.mpg.de/toc/z2007_1211.pdf.
[2] FORTUNATO S.Community detection in graphs[J].Physics Reports,2010,486(3-5):75-174.
[3] BOTHOREL C,CRUZ J D,MAGNANI M,et al.Clustering attributed graphs:Models,measures and methods[J].Network Science,2015,3(3):408-444.
[4] YANG J,MCAULEY J,LESKOVEC J.Community Detectionin Networks with Node Attributes[J/OL].http://www-cs.stonford.edu/peole/jure/pubs/cesna-icdm13.pdf.
[5] LI Q,ZHU Q,WANG M.Design of a distributed energy-efficient clustering algorithm for heterogeneous wireless sensor networks[J].Journal of Software,2006,29(12):2230-2237.
[6] WANG W,JIANG J,AN B,et al.Toward Efficient Team Formation for Crowdsourcingin Noncooperative Social Networks[J].IEEE Transactions on Cybernetics,2016,pp(99):1-15.
[7] 李钝,李伦,张行进,等.一种基于结构和属性的图聚类算法研究[J].小型微型计算机系统,2016,37(7):1469-1473.
[8] LIU J,JIN X,TSUI K C.Autonomy-oriented computing (AOC):formulating computational systems with autonomous components[J].IEEE Transactions on Systems Man and Cybernetics-Part A Systems and Humans,2005,35(6):879-902.
[9] III J J P,MORENO S,FOND T L,et al.Attributed Graph Mo-dels:Modeling network structure with correlated attributes[J/OL].http://www.conference.org/proceedings/www2014/proceedings/p831.pdf.
[10] BERLINGERIO M,PINELLI F,CALABRESE F.ABACUS:Apriori-Based Community discovery in mUltidimensional networkS[J].Data Mining & Knowledge Discovery,2013,27(27):294-320.
[11] 张昕尧,高宏.一种新的属性图重叠聚类挖掘算法[J].智能计算机与应用,2012,2(5):27-30.
[12] RUAN Y,FUHRY D,PARTHASARATHY S.Efficient Community Detection in Large Networks using Content and Links[C]∥ International Conference on World Wide Web.2012:1089-1098.
[13] ZANGHI H,VOLANT S,AMBROISE C.Clustering based on random graph model embedding vertex features[J].Pattern Recognition Letters,2009,31(9):830-836.
[14] XU Z,KE Y,WANG Y,et al.A model-based approach to attri-buted graph clustering[C]∥ACM Sigmod International Con-ference on Management of Data.2012:505-516.
[15] GNNEMANN S,BODEN B,FRBER I,et al.Efficient Mi-ning of Combined Subspace and Subgraph Clusters in Graphs with Feature Vectors[M]∥Advances in Knowledge Discovery and Data Mining.2013:261-275.
[16] 吴烨,钟志农,熊伟,等.一种高效的属性图聚类方法[J].计算机学报,2013,36(8):1704-1713.
[17] YANG B,LIU J,LIU D.An autonomy-oriented computing approach to community mining in distributed and dynamic networks[J].Autonomous Agents and Multi-Agent Systems,2010,20(2):123-157.
[18] BU Z,WU Z,CAO J,et al.Local Community Mining on Distri-buted and Dynamic Networks From a Multiagent Perspective[J].IEEE Transactions on Cybernetics,2015,6(4):986-999.
[19] PRATPEREZ A,DOMINGUEZSAL D,L ARRIBAPEY J,et al.High quality,scalable and parallel community detection for large real graphs[C]∥World Wide Web.2014:225-236.
[20] YANG J,LESKOVEC J.Overlapping community detection atscale:a nonnegative matrix factorization approach[C]∥ACM International Conference on Web Search and Data Mining.2013:587-596.
[21] 张素智,张琳,曲旭凯.基于最短路径的加权属性图聚类算法研究[J].计算机应用与软件,2016,33(11):212-214.
[22] LI H J,BU Z,LI A,et al.Fast and accurate mining the community structure:integrating center locating and membership optimization[J].IEEE Transactions on Knowledge & Data Engineering,2016,28(9):2349-3362.
[23] LI H J,DANIELS J J.Social significance of community structure:Statistical view[J].Physical Review E Statistical Nonli-near & Soft Matter Physics,2015,91(1):012801.

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75, 88 .
[2] XIA Qing-xun and ZHUANG Yi. Remote Attestation Mechanism Based on Locality Principle[J]. Computer Science, 2018, 45(4): 148 -151, 162 .
[3] LI Bai-shen, LI Ling-zhi, SUN Yong and ZHU Yan-qin. Intranet Defense Algorithm Based on Pseudo Boosting Decision Tree[J]. Computer Science, 2018, 45(4): 157 -162 .
[4] WANG Huan, ZHANG Yun-feng and ZHANG Yan. Rapid Decision Method for Repairing Sequence Based on CFDs[J]. Computer Science, 2018, 45(3): 311 -316 .
[5] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[6] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[7] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[8] LIU Qin. Study on Data Quality Based on Constraint in Computer Forensics[J]. Computer Science, 2018, 45(4): 169 -172 .
[9] ZHONG Fei and YANG Bin. License Plate Detection Based on Principal Component Analysis Network[J]. Computer Science, 2018, 45(3): 268 -273 .
[10] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J]. Computer Science, 2018, 45(4): 94 -99, 116 .