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

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

0 引言

　　物以類聚，人以群分。許多社會網(wǎng)絡隨著時間逐漸演變形成它們自身的社區(qū)。它們有一個共同特性——社區(qū)結(jié)構。整個網(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ū)結(jié)構定義[7]，兩者的關聯(lián)系數(shù)越小，同時內(nèi)部連接值越大，之間連接值越小，則劃分結(jié)果越好。本文利用該思想首先闡述了在劃分算法中占重要位置的關聯(lián)系數(shù)，然后提出基于此的算法，最后將算法實驗于城市社區(qū)劃分應用場景，并將本文算法與基于Q值的社區(qū)劃分算法結(jié)果進行比較，結(jié)果表明本文提出的算法是切實可行且有效的。

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

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

　　定義 信息圖[8]：包含n個節(jié)點的圖G=（V，E，M），V是節(jié)點集合，節(jié)點vi有屬性集VA={va1，va2，…，vam}。E是邊集合，邊ei有屬性集EA={ea1，ea2，…，eal}。M為兩節(jié)點共享鄰居節(jié)點數(shù)的矩陣，簡稱共鄰矩陣，矩陣元素Mij=eikekj，其中eik、ekj分別表示vi和vk、vj和vk之間是否存在鏈接。

　　信息圖的連接強度矩陣元素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時刻兩曲線的關聯(lián)系數(shù)越小，兩者相關性越小。

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

　　2.1 算法定義

　?。?）節(jié)點屬性

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

　　（2）鏈接屬性

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

　　（3）共鄰屬性

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

　?。?）連接強度

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

　?。?）互信息量NMI[9]

　　NMI是社區(qū)結(jié)構已知的算法評價標準，即算法發(fā)現(xiàn)社區(qū)結(jié)構與真實社區(qū)結(jié)構的一致性程度。若兩者完全一致，則NMI為1，通常NMI∈（0，1）。定義公式為：

　πa、πb分別表示真實社區(qū)和算法發(fā)現(xiàn)的社區(qū)結(jié)構。k（a）表示社區(qū)結(jié)構πa中的社區(qū)數(shù)量，nha表示社區(qū)結(jié)構πa中第h個社區(qū)的節(jié)點數(shù)，nh，l表示同時在πa中的第h個社區(qū)，πb中的第l個社區(qū)的節(jié)點個數(shù)。

　　2.2 算法實現(xiàn)

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

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

　　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ū)結(jié)構越穩(wěn)定。

　　Inter（ij）和Exter（ij）關聯(lián)系數(shù)計算公式如下：

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

3 實驗及分析

　?。?）數(shù)據(jù)預處理

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

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

　?。?）參數(shù)選擇

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

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

　?。?）實驗分析

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

　　利用式（10）將該權重分配與其余4組隨機數(shù)比較，得到結(jié)果如表1所示。

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

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

4 結(jié)論

　　本文針對社區(qū)結(jié)構發(fā)現(xiàn)問題，提出了基于關聯(lián)系數(shù)的社區(qū)劃分算法。該算法在綜合考慮節(jié)點屬性、鏈接屬性和共鄰屬性的基礎上，計算社區(qū)內(nèi)部和之間的連接強度，并計算兩者的關聯(lián)系數(shù)，依次選擇關聯(lián)系數(shù)最小的節(jié)點對進行凝聚。此外，將該算法實驗于城市社區(qū)，劃分出的社區(qū)結(jié)構與真實結(jié)構相比具有較高的準確性。但是，本文算法復雜度較高，適用于中小型網(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 efficient spectral algorithm for network community discovery and its applications to biological and social networks[C]. Seventh IEEE International Conference on Data Mining， ICDM 2007， 2007：643-648.

　　[5] KERNIGHAN B W， LIN S. An efficient heuristic 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， et al. 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]. Physical Review， 2004，70（6）：66-111.

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