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

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

0 引言

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

　　社區(qū)劃分的研究迄今已有很長(zhǎng)歷史，學(xué)者們已研究出多種劃分算法，如GN分裂算法[2]，Newman快速算法[3]、基于Laplace矩陣的譜平分算法[4]、Kernighan-Lin算法[5]等。這些算法有一共性：用模塊度量Q[6]作為算法終止條件，同時(shí)也作為衡量社區(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ù)越小，同時(shí)內(nèi)部連接值越大，之間連接值越小，則劃分結(jié)果越好。本文利用該思想首先闡述了在劃分算法中占重要位置的關(guān)聯(lián)系數(shù)，然后提出基于此的算法，最后將算法實(shí)驗(yàn)于城市社區(qū)劃分應(yīng)用場(chǎng)景，并將本文算法與基于Q值的社區(qū)劃分算法結(jié)果進(jìn)行比較，結(jié)果表明本文提出的算法是切實(shí)可行且有效的。

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

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

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

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

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

　　設(shè)有曲線sin（t）和cos（t），取t=0，1，2，…，10時(shí)刻的正、余弦序列{sin（0），sin（1），…，sin（10）}，{cos（0），cos（1），…，cos（10）}，則兩曲線在各t時(shí)刻的關(guān)聯(lián)系數(shù)如下：

　　其中，（min）和（max）為兩曲線在同一時(shí)刻對(duì)應(yīng)的最小差和最大差；（t）為兩曲線在t時(shí)刻的序列差；ρ為分辨系數(shù)，在0~1之間，通常取0.5。

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

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

　　2.1 算法定義

　?。?）節(jié)點(diǎn)屬性

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

　　（2）鏈接屬性

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

　　（3）共鄰屬性

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

　?。?）連接強(qiáng)度

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

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

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

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

　　2.2 算法實(shí)現(xiàn)

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

　　兩者的計(jì)算公式分別如下：

　　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ù)越小，同時(shí)Inter（ij）越大、Exter（ij）越小時(shí)，表明社區(qū)內(nèi)部的連接強(qiáng)度越大于外部，將該節(jié)點(diǎn)對(duì)凝聚至同一社區(qū)，會(huì)使得社區(qū)結(jié)構(gòu)越穩(wěn)定。

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

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

3 實(shí)驗(yàn)及分析

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

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

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

　　（2）參數(shù)選擇

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

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

　?。?）實(shí)驗(yàn)分析

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

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

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

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

4 結(jié)論

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

參考文獻(xiàn)

　　[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 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é)點(diǎn)與鏈接屬性的社交網(wǎng)絡(luò)社區(qū)劃分算法[J].計(jì)算機(jī)應(yīng)用研究，2013，30（5）：1477-1480.