计算机科学 ›› 2017, Vol. 44 ›› Issue (Z6): 433-437.doi: 10.11896/j.issn.1002-137X.2017.6A.097
石铠,任泺锟,彭一鸣,李慧嘉
SHI Kai, REN Luo-kun, PENG Yi-ming and LI Hui-jia
摘要： 属性图用属性向量描述节点,用边描述节点间的关系。为了把节点划分为具有紧密联系的社团,一种有效的方法是对属性图进行聚类。聚类方法有不同的标准,如节点连接度和属性相似度。虽然社团一般是围绕紧密的连边和相似的属性值的节点形成,但是目前的方法都只关注了这两种数据形式中的一种。通过给每个节点赋予一个自治域,提出一个准确且可延展的多节点系统用于提取属性图中的重叠社团。首先,引入带有可调带宽因子的核函数用于测度每个节点的影响力,具有最高局部影响力的节点可以被看作领导节点。其次,提出一种新颖的局部扩展策略,使每一个领导节点能够吸收属性图中相关性最强的跟随者。接着,设计了多节点社团意识系统,该系统为节点之间的充分沟通提供了必要的条件,从而能够得出最优的重叠社团结构。社团中的节点不仅互相联系紧密,而且也有相似的属性。该算法的计算复杂度在特定带宽条件下近似于连边数目的线性函数。最后,基于标准属性图和真实属性图的实验验证了该系统的有效性和高效性。
| [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] GNNEMANN S,BODEN B,FRBER 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! |
|
||
首页