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

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

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

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

衡量標(biāo)準(zhǔn)；模塊度；關(guān)聯(lián)系數(shù)；社區(qū)結(jié)構(gòu)

0 引言

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

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

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

1 社會網(wǎng)絡(luò)結(jié)構(gòu)相關(guān)定義

1.1 社會網(wǎng)絡(luò)結(jié)構(gòu)

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

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

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

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

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

2.1 算法定義

（1）節(jié)點屬性

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

（2）鏈接屬性

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

（3）共鄰屬性

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

（4）連接強(qiáng)度

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

（5）互信息量NMI［9］

2.2 算法實現(xiàn)

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

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

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

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

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

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

圖2 算法流程

3 實驗及分析

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

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

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

（2）參數(shù)選擇

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

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

（3）實驗分析

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

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

表1 參數(shù)比較

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

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

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

4 結(jié)論

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

［1］鄭浩原，黃戰(zhàn).復(fù)雜網(wǎng)絡(luò)社區(qū)挖掘——改進(jìn)的層次聚類算法［J］.微型機(jī)與應(yīng)用，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)絡(luò)社區(qū)劃分算法［J］.計算機(jī)應(yīng)用研究，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

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

2015-03-19）

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

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

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