基于關聯(lián)系數(shù)的社區(qū)劃分算法

顧宏博，奚杰杰，吳 晶（南京郵電大學 通信與信息工程學院，江蘇 南京 210003）

基于關聯(lián)系數(shù)的社區(qū)劃分算法

顧宏博，奚杰杰，吳 晶
（南京郵電大學 通信與信息工程學院，江蘇 南京 210003）

不同于一般社區(qū)劃分衡量標準——模塊度Q值，從社區(qū)結構本質(zhì)出發(fā)，提出一種用關聯(lián)系數(shù)評判社區(qū)劃分好壞的方法，即求社區(qū)內(nèi)部連接與外部連接的關聯(lián)系數(shù)。該方法不但能克服模塊度Q值只適用于無向無權網(wǎng)絡的缺陷，而且更符合社區(qū)結構的定義。

衡量標準；模塊度；關聯(lián)系數(shù)；社區(qū)結構

0 引言

物以類聚，人以群分。許多社會網(wǎng)絡隨著時間逐漸演變形成它們自身的社區(qū)。它們有一個共同特性——社區(qū)結構。整個網(wǎng)絡由若干社區(qū)構成，每個社區(qū)內(nèi)部節(jié)點之間的連接相對緊密，而社區(qū)之間的節(jié)點連接相對稀疏［1］。

社區(qū)劃分的研究迄今已有很長歷史，學者們已研究出多種劃分算法，如GN分裂算法［2］，Newman快速算法［3］、基于Laplace矩陣的譜平分算法［4］、Kernighan-Lin算法［5］等。這些算法有一共性：用模塊度量Q［6］作為算法終止條件，同時也作為衡量社區(qū)劃分好壞的標準。

受Q值啟發(fā)，衡量標準也可從社區(qū)內(nèi)部連接強度與社區(qū)之間連接強度的關聯(lián)系數(shù)出發(fā)，能直觀地符合社區(qū)結構定義［7］，兩者的關聯(lián)系數(shù)越小，同時內(nèi)部連接值越大，之間連接值越小，則劃分結果越好。本文利用該思想首先闡述了在劃分算法中占重要位置的關聯(lián)系數(shù)，然后提出基于此的算法，最后將算法實驗于城市社區(qū)劃分應用場景，并將本文算法與基于Q值的社區(qū)劃分算法結果進行比較，結果表明本文提出的算法是切實可行且有效的。

1 社會網(wǎng)絡結構相關定義

1.1 社會網(wǎng)絡結構

信息圖的連接強度矩陣元素Aij表示vi和vj的連接強度，它綜合了節(jié)點屬性、鏈接屬性和共鄰屬性。

1.2 關聯(lián)系數(shù)定義

設有曲線sin（t）和cos（t），取t=0，1，2，…，10時刻的正、余弦序列｛sin（0），sin（1），…，sin（10）｝，｛cos（0），cos（1），…，cos（10）｝，則兩曲線在各t時刻的關聯(lián)系數(shù)如下：其中，Δ（min）和Δ（max）為兩曲線在同一時刻對應的最小差和最大差；Δ（t）為兩曲線在 t時刻的序列差；ρ為分辨系數(shù)，在0～1之間，通常取0.5。

ζ（t）越小，即在t時刻兩曲線的關聯(lián)系數(shù)越小，兩者相關性越小。

2 基于關聯(lián)系數(shù)的社區(qū)劃分算法

2.1 算法定義

（1）節(jié)點屬性

vi和vj屬性集為 VAi和VAj，構成帶夾角的空間向量，夾角越小表明兩節(jié)點屬性越相似。因此，用夾角余弦計算屬性相似度：

（2）鏈接屬性

為與實驗數(shù)據(jù)保持一致，這里用簡單的距離dij表示vi和vj的鏈接屬性，并用最大距離 dmax將其歸一化：

（3）共鄰屬性

兩節(jié)點的共鄰數(shù)目越多，表明它們的間接聯(lián)系會越頻繁，則劃分至同一社區(qū)的概率會變大。因此共鄰屬性為：

（4）連接強度

節(jié)點之間連接強度綜合考慮三因素：

（5）互信息量NMI［9］

2.2 算法實現(xiàn)

社會網(wǎng)絡中節(jié)點的連接強度如圖1所示，判斷兩節(jié)點能否凝聚至同一社區(qū)，需計算社區(qū)內(nèi)部連接強度Inter（ij）和外部連接強度Exter（ij）之間的關聯(lián)系數(shù)。

圖1 節(jié)點內(nèi)外連接強度定義

兩者的計算公式分別如下：

Inter（ij）表示社區(qū)內(nèi)部連接強度占所有連接強度之比，Exter（ij）表示與社區(qū)內(nèi)部相連的外部連接強度占所有連接強度之比。當Inter（ij）和Exter（ij）關聯(lián)系數(shù)越小，同時Inter（ij）越大、Exter（ij）越小時，表明社區(qū)內(nèi)部的連接強度越大于外部，將該節(jié)點對凝聚至同一社區(qū)，會使得社區(qū)結構越穩(wěn)定。

Inter（ij）和Exter（ij）關聯(lián)系數(shù)計算公式如下：其中，Δ（ij）=Inter（ij）-Exter（ij）。

基于關聯(lián)系數(shù)的社區(qū)劃分算法（Community Detection Algorithm Based OnCorrelation Coefficients，CDACC））采用凝聚思想，逐步將社區(qū)節(jié)點對進行凝聚，具體的處理流程如圖2所示。

圖2 算法流程

3 實驗及分析

（1）數(shù)據(jù)預處理

獲取南京市主城區(qū)數(shù)據(jù)，視各區(qū)內(nèi)的社區(qū)為節(jié)點，抓取節(jié)點屬性｛人口、年齡、人均占地面積｝和節(jié)點之間距離。

約束條件：以vi為中心，長度D為直徑作圓，則在圓形區(qū)域內(nèi)的節(jié)點記為vi的鄰居節(jié)點。

（2）參數(shù)選擇

式（5）中的參數(shù)α、β、γ用單一屬性方法獲取，即假設認為只有節(jié)點屬性對社區(qū)劃分有影響，計算得最優(yōu)關聯(lián)系數(shù)和ζ1；同理得鏈接屬性和共鄰屬性的最優(yōu)關聯(lián)系數(shù)和ζ2、ζ3。ζ越小，表明該屬性對社區(qū)劃分的影響力越大。因此，參數(shù)α、β、γ的權重分配為：

由于本文算法是受基于Q的凝聚算法啟發(fā)，故將本文算法與經(jīng)典凝聚算法——CNM［10］、凝聚算法的改進CDASW［11］進行比較，并利用互信息量衡量劃分結果。

（3）實驗分析

首先，用單一屬性法得ζ1=3.665 9，ζ2=3.543 4，ζ3=4.328 8。由此看出：在城市社區(qū)中，鏈接屬性、節(jié)點屬性、共鄰屬性對劃分結果影響力依次減小。

利用式（10）得α、β、γ之比，歸一化為α=0.347 0，β=0.359 1，γ=0.293 9。將該權重分配與其余4組隨機數(shù)比較，得到結果如表1所示。

表1 參數(shù)比較

因此，在最優(yōu)參數(shù)條件下，將本文算法 CDACC、CNM、CDASW劃分結果與真實城市社區(qū)結構進行比較，結果如圖3所示。

圖3 社區(qū)劃分算法比較

由圖3可知，在城市社區(qū)中，CDACC、CDASW、CNM算法的劃分準確率依次降低，這不僅驗證了城市社區(qū)的劃分需要綜合考慮節(jié)點屬性、鏈接屬性和共鄰屬性，還證明了CDACC算法的切實可行性。

4 結論

本文針對社區(qū)結構發(fā)現(xiàn)問題，提出了基于關聯(lián)系數(shù)的社區(qū)劃分算法。該算法在綜合考慮節(jié)點屬性、鏈接屬性和共鄰屬性的基礎上，計算社區(qū)內(nèi)部和之間的連接強度，并計算兩者的關聯(lián)系數(shù)，依次選擇關聯(lián)系數(shù)最小的節(jié)點對進行凝聚。此外，將該算法實驗于城市社區(qū)，劃分出的社區(qū)結構與真實結構相比具有較高的準確性。但是，本文算法復雜度較高，適用于中小型網(wǎng)絡。因此，需要進一步探討算法，減少其復雜度，以便能夠適用于各種大型的復雜網(wǎng)絡。

［1］鄭浩原，黃戰(zhàn).復雜網(wǎng)絡社區(qū)挖掘——改進的層次聚類算法［J］.微型機與應用，2011，30（16）：85-88.

［2］NEWMAN M E J，GIRVAN M.Finding and evaluating community structure in networks［J］.Physical Revew E，2004，69（2）：26113.

［3］NEWMAN M E J.Fast algorithm for detecting community structure in networks［J］.Physical Review E，2004，69：06613.

［4］ Ruan Jianhua， Zhang Weixiong.An efficientspectral algorithm for network community discovery and its applications to biological and social networks［C］.Seventh IEEE InternationalConference on DataMining， ICDM 2007，2007：643-648.

［5］ KERNIGHAN B W， LIN S.An efficientheuristic procedure for partitioning graphs［J］.Bell System Technical Journal，1970，49（2）：291-307.

［6］NEWMAN M E J.Modularity and community structure in networks［J］.Proc Natl Acad Sci USA，48109-1040，2006，103（23）：8577-8582.

［7］NEWMAN M E J.Detecting community structure in networks［J］.The European Physical Journal B，2004，38：321-330.

［8］Tang Jin， Jiang Bo， Chang Chinchen， etal.Graph structure analysis based on complex network ［J］.Digital Signal Processing，2012，22（5）：713-725.

［9］ALCOSER，JEFFREY J.Behind our sociality（or social capital）：evolution，the rule of 150，and reading others［J］. Behind our sociality，2014，8（5）：18-25.

［10］CLAUSET A，NEWMAN J，MOORE C.Finding community structure in very large networks［J］.PhysicalReview，2004，70（6）：66-111.

［11］李孝偉，陳福才，劉力雄.一種融合節(jié)點與鏈接屬性的社交網(wǎng)絡社區(qū)劃分算法［J］.計算機應用研究，2013，30（5）：1477-1480.

Partition methods based on correlation coefficients for the community structure in social networks

Gu Hongbo，Xi Jiejie，Wu Jing
（School of Telecommunication and Information Engineering，Nanjing University of Posts and Telecommunications，Nanjing 210003，China）

Different from general measures of quality standards for the community structure—modularity Q，this paper proposed a new method based on the essence of community structure called correlation coefficients which is the correlation between internal and external links to measure the division.This method can not only overcome the defects of modularity Q which applies only to undirect and unweighted network，but also can be in line with the definition of community structure better.

quality standards；modularity；correlation coefficients；community structure

TP301.6

A

1674-7720（2015）18-0017-03

顧宏博，奚杰杰，吳晶.基于關聯(lián)系數(shù)的社區(qū)劃分算法［J］.微型機與應用，2015，34（18）：17-19.

2015-03-19）

顧宏博（1990-），通信作者，女，碩士研究生，主要研究方向：社會網(wǎng)絡。E-mail：ghb925975754@163.com。

奚杰杰（1990-），男，碩士研究生，主要研究方向：社會網(wǎng)絡。

吳晶（1990-），女，碩士研究生，主要研究方向：社會網(wǎng)絡。