电子学报
電子學報
전자학보
ACTA ELECTRONICA SINICA
2015年
8期
1575-1582
,共8页
王诗懿%董一鸿%李志超%陈华辉%钱江波
王詩懿%董一鴻%李誌超%陳華輝%錢江波
왕시의%동일홍%리지초%진화휘%전강파
大规模复杂网络%GraphLab%重叠社区识别%社会网络%核心社区
大規模複雜網絡%GraphLab%重疊社區識彆%社會網絡%覈心社區
대규모복잡망락%GraphLab%중첩사구식별%사회망락%핵심사구
large-scale complex network%GraphLab%overlapping community identification%social network%kernel communi-ty
随着网络规模的不断扩大,经典的复杂网络重叠社识别算法已不能高效处理现有的大规模网络图数据。本文在 GraphLab 并行计算模型上提出了基于重要节点扩展的重叠社区识别算法 DOCVN (Detecting the Overlapping Community algorithm based on Vital Node Expanding in GraphLab)。算法选取网络中 PageRank 值大的节点作为重要节点,计算其他节点归属于重要节点的节点归属度,并以重要节点为中心形成核心社区及扩展社区,最后根据重要节点间的连接紧密度合并核心社区及扩展社区,并计算出每个节点在所属社区里的节点重要度,实现了大规模网络的重叠社区识别。实验表明该算法与 PD (Propinquity Dynamics)等现有并行算法相比更能有效地识别大规模网络的重叠社区结构。
隨著網絡規模的不斷擴大,經典的複雜網絡重疊社識彆算法已不能高效處理現有的大規模網絡圖數據。本文在 GraphLab 併行計算模型上提齣瞭基于重要節點擴展的重疊社區識彆算法 DOCVN (Detecting the Overlapping Community algorithm based on Vital Node Expanding in GraphLab)。算法選取網絡中 PageRank 值大的節點作為重要節點,計算其他節點歸屬于重要節點的節點歸屬度,併以重要節點為中心形成覈心社區及擴展社區,最後根據重要節點間的連接緊密度閤併覈心社區及擴展社區,併計算齣每箇節點在所屬社區裏的節點重要度,實現瞭大規模網絡的重疊社區識彆。實驗錶明該算法與 PD (Propinquity Dynamics)等現有併行算法相比更能有效地識彆大規模網絡的重疊社區結構。
수착망락규모적불단확대,경전적복잡망락중첩사식별산법이불능고효처리현유적대규모망락도수거。본문재 GraphLab 병행계산모형상제출료기우중요절점확전적중첩사구식별산법 DOCVN (Detecting the Overlapping Community algorithm based on Vital Node Expanding in GraphLab)。산법선취망락중 PageRank 치대적절점작위중요절점,계산기타절점귀속우중요절점적절점귀속도,병이중요절점위중심형성핵심사구급확전사구,최후근거중요절점간적련접긴밀도합병핵심사구급확전사구,병계산출매개절점재소속사구리적절점중요도,실현료대규모망락적중첩사구식별。실험표명해산법여 PD (Propinquity Dynamics)등현유병행산법상비경능유효지식별대규모망락적중첩사구결구。
With the unceasing expanding of network scale,many classic detection algorithms of overlapping communities cannot work efficiently in large-scale complex network.Detecting the overlapping community algorithm based on vital node expand-ing in parallel framework GraphLab (DOCVN)is introduced to identify the overlapping communities.In this algorithm,nodes with high PageRank value are regarded as vital nodes,and then the affiliation degree of other nodes to these vital nodes are computed. After that,kernel communities and expanding communities are identified respectively.Finally,the kernel communities and expanding communities are combined into some overlapping communities by judging whether they connect tightly.And the importance weight of each node in its community is also computed.Experimental results show that the algorithm is more effective than the existing par-allel algorithms like PD (Propinquity Dynamics)to identify large-scale overlapping communities.