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

Previous Articles     Next Articles

Distributed and Heterogeneous Multi-agent System for Attributed Graph Clustering

BIAN Zhai-an, LI Hui-jia, CHEN Jun-hua, MA Yu-han and ZHAO Dan   

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

Abstract: Recent years have witnessed a renewed attention towards attributed graph clustering,which aims to divide the nodes in the attribute graph into several clusters,so that each cluster has a densely connected intra-cluster structure and homogeneous attribute values.Existing methods ignore nodes/objects selfish nature in real-life contexts.Meanwhile,some open problems,such as heterogeneous information integration,high computational cost,etc.,have not been effectively resolved yet.To this end,we considered the attribute graph clustering problem as the cluster formation game of selfish node-agents.To effectively integrate both topological and attributive information,we proposed both tightness and homogeneity constraints on node-agents’ strategy selection.To be specific,the game process will converge to weakly Pareto-Nash equilibrium almost surely.In the aspect of implement,we carefully designed a distributed and heterogeneous multiagent system,based on which,a fast distributed learning algorithm is also given.The main feature of the proposed algorithm is that the overlap rate of the resulted partition can be well controlled by a pre-specified threshold.Finally,we conducted a set of simulation experiments on real-life social networks and comparisons are listed.

Key words: Attributed graph clustering,Cluster formation game,Tightness and homogeneity constraints,Distributed learning algorithm,Multiagent system

[1] BOTHOREL C,CRUZ J D,MAGNANI M,et al.Clustering attributed graphs:Models,measures and methods[J].Network Science,2015,3(3):408-444.
[2] LI Q,ZHI 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.
[3] Fortunato S.Community detection in graphs[J].Physics Reports,2010,486(3-5):75-174.
[4] CLAUSET A,NEWMAN M E,MOORE C.Finding communitystructure in very large networks[J].Physical Review E, 2005,70(6Pt 2):264-277.
[5] BLONDEL V D,GUILLAUME J L,LAMBIOTTE R,et al.Fastunfolding of communities in large networks[J].Journal of Statistical Mechanics Theory & Experiment,2008,2008(10):155-168.
[6] BARTHELEMY M,FORTUNATO S.Resolution limit in community detection[J].Proceedings of the National Academy of Sciences of the United States of America,2007,104(1):36-41.
[7] ALDECOA R,MARN I.Surprise maximization reveals the com-munity structure of complex networks[J].Scientific Reports,2013,3(1):173-185.
[8] CLAUSET A.Finding local community structure in networks[J].Physical Review E Statistical Nonlinear&Soft Matter Phy-sics,2005,72(2):254-271.
[9] LUO F,WANG J Z,PROMISLOW E.Exploring local community structures in large networks[J].Web Intelligence & Agent Systems,2006,6(4):387-400.
[10] HUANG J,SUN H,LIU Y,et al.Towards online multiresolution community detection in large-scale networks[J].Plos One,2011,6(8):492-492.
[11] LI K,PANG Y.A vertex similarity probability model for finding network community structure[C]∥PAKDD.2012:456-467.
[12] CHEN H H,GOU L,ZHANG X,et al.Discovering missinglinks in networks using vertex similarity measures[C]∥ACM Symposium on Applied Computing.2012:138-143.
[13] COMBE D,LARGERON C,E GYED-ZSIGMOND E,et al.Combining relations and text in scientific network clustering[C]∥International Conference on Advances in Social Networks Ana-lysis and Mining.2012:1248-1253.
[14] ZHOU Y,CHENG H,YU J X.Graph Clustering Based onStructural/Attribute Similarities[J].Proceedings of the Vldb Endowment,2009,2(1):718-729.
[15] CHENG H,ZHOU Y,YU J X.Clustering large attributedgraphs:A balance between structural and attribute similarities[J].ACM Transactions on Knowledge Discovery from Data,2011,5(2):190-205.
[16] ZHOU Y,CHENG H,YU J X.Clustering large attributedgraphs:An efficient incremental approach[C]∥2013 IEEE 13th International Conference on Data Mining.2010:689-698.
[17] III J J P,MORENO S,FOND T L,et al.Attributed graph mo-dels:Modeling network structure with correlated attributes[C]∥Proceedings of the 23rd International Conference on World Wide Web.ACM,2014:831-842.
[18] ZANGHI H,VOLANT S,AMBROISE C.Clustering based on random graph model embedding vertex features[J].Pattern RecognitionLetters,2010,31(9):830-836.
[19] XU Z,KE Y,WANG Y,et al.A model-based approach to attri-buted graph clustering[C]∥Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data.ACM,2012:505-516.
[20] GUNNEMANN S,FARBER I,BODEN B,et al.Subspace clustering meets dense subgraph mining:A synthesis of two paradigms[C]∥IEEE International Conference on Data Mining.2010:845-850.

No related articles found!
Full text



[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 .