徐 兵，趙亞偉，徐楊遠(yuǎn)翔

(1.中國科學(xué)院大學(xué)大數(shù)據(jù)分析技術(shù)實(shí)驗(yàn)室，北京 100049；2.北京知因智慧數(shù)據(jù)科技有限公司AI實(shí)驗(yàn)室，北京 100027)

0 引言

隨著中國經(jīng)濟(jì)的快速增長和信息技術(shù)的不斷進(jìn)步，人們生活水平日益提高，人與人之間、企業(yè)與企業(yè)之間的聯(lián)系也越來越緊密，這導(dǎo)致各種關(guān)系形成的網(wǎng)絡(luò)越來越多、越來越復(fù)雜。網(wǎng)絡(luò)結(jié)構(gòu)的分析對于洞悉網(wǎng)絡(luò)背后的復(fù)雜關(guān)系起到了非常關(guān)鍵的作用。近年來，許多專家、學(xué)者在進(jìn)行復(fù)雜網(wǎng)絡(luò)分析、網(wǎng)絡(luò)研究時(shí)發(fā)現(xiàn)，大多真實(shí)網(wǎng)絡(luò)都存在社團(tuán)結(jié)構(gòu)[1]這一特性——同一社團(tuán)里成員聯(lián)系更緊密、交流更頻繁，而不同社團(tuán)成員之間聯(lián)系相對稀疏、交流較少。社團(tuán)結(jié)構(gòu)在不同領(lǐng)域里也有不同的稱謂，如在社交網(wǎng)絡(luò)領(lǐng)域，社團(tuán)結(jié)構(gòu)大多被稱為“朋友圈”；在銀行業(yè)被稱為“客戶群”；還有組、群、類等稱謂。挖掘網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)并追蹤社團(tuán)演化的序列模式，對于了解網(wǎng)絡(luò)功能具有極其重要的意義。社交網(wǎng)絡(luò)分析也是目前研究的熱點(diǎn)之一，作為人類真實(shí)世界在網(wǎng)絡(luò)虛擬世界的一種延伸，群組結(jié)構(gòu)是社交網(wǎng)絡(luò)的一個(gè)重要結(jié)構(gòu)特征，也是中觀尺度下觀察和理解網(wǎng)絡(luò)拓?fù)涞囊环N重要結(jié)構(gòu)，這種結(jié)構(gòu)無論對于學(xué)術(shù)界還是工業(yè)界都有巨大的研究價(jià)值[2-3]。社團(tuán)研究還可應(yīng)用在銀行業(yè)中，在銀行客戶關(guān)系網(wǎng)絡(luò)中，存在著許多具有相關(guān)關(guān)系的客戶。這些客戶組成的客戶區(qū)，因其龐大的規(guī)模、巨額的資金需求等因素成為商業(yè)銀行信貸資金爭相追捧的對象，也是銀行利潤的重要源泉。因此，對于銀行客戶群的識別與追蹤就顯得尤為重要。

本文首先提出社團(tuán)里的成員并非完全對等，而是有核心與非核心成員之分。在某些情況下，核心成員可能對社團(tuán)產(chǎn)生或消失有著更大的影響。并且社團(tuán)結(jié)構(gòu)并非是一成不變的，而是處于不斷變化中。如社團(tuán)成員數(shù)量的增加或減少、社團(tuán)核心成員的出現(xiàn)或消失、社團(tuán)的其他一些屬性的變化等。為了追蹤這種變化以及社團(tuán)是如何演化的，本文從普遍意義上的關(guān)聯(lián)群出發(fā)，首先對關(guān)聯(lián)群給出了明確定義，并闡述了關(guān)鍵演化事件、演化序列的相關(guān)概念。在此基礎(chǔ)之上，提出基于關(guān)聯(lián)群演化相似度的社團(tuán)追蹤算法，識別出演化過程中形成的關(guān)聯(lián)群以及演化序列。最后，對上述的算法進(jìn)行了實(shí)驗(yàn)分析。實(shí)驗(yàn)結(jié)果表明，所提出的算法可實(shí)現(xiàn)關(guān)聯(lián)群的精準(zhǔn)識別與演化序列的準(zhǔn)確生成。

本文剩下內(nèi)容包括以下4個(gè)部分。第2部分主要對社團(tuán)結(jié)構(gòu)的相關(guān)研究進(jìn)行了分析總結(jié)。在第3部分中，對關(guān)聯(lián)群以及相關(guān)定義進(jìn)行闡述說明，并對關(guān)聯(lián)群追蹤算法給出詳細(xì)的描述。第4部分通過一個(gè)具體實(shí)例對上述算法進(jìn)行驗(yàn)證分析，并給出了相應(yīng)的一些結(jié)論建議。第5部分對本文進(jìn)行了總結(jié)以及對未來研究進(jìn)行展望。

1 相關(guān)工作

隨著Facebook、Twitter、微博、QQ、微信等各種SNS(Social Network Service)的流行與興起，社團(tuán)結(jié)構(gòu)的分析變得非常熱門。社團(tuán)結(jié)構(gòu)一直是社會(huì)學(xué)研究的一個(gè)重要課題，而在計(jì)算機(jī)領(lǐng)域，社團(tuán)結(jié)構(gòu)的研究主要體現(xiàn)在社交網(wǎng)絡(luò)的分析上。社交網(wǎng)絡(luò)分析中最常見的是社交圈的識別。Facebook和微信是關(guān)于人與人之間的強(qiáng)關(guān)系網(wǎng)絡(luò)，劃分社交圈有助于朋友間相互推薦。微博、Twitter、豆瓣、微信公眾號是關(guān)于關(guān)注與被關(guān)注的弱關(guān)系網(wǎng)絡(luò)，劃分關(guān)聯(lián)群有助于消息和知識的傳播[4-5]。劃分社團(tuán)之后還可以對客戶進(jìn)行精準(zhǔn)化營銷，與推薦系統(tǒng)中的基于用戶的協(xié)同過濾算法相結(jié)合，為用戶推薦個(gè)性化的商品和服務(wù)；甚至可以識別互聯(lián)網(wǎng)金融業(yè)中的欺詐團(tuán)伙，進(jìn)行欺詐團(tuán)伙檢測[6-8]；另外，也可以追蹤社團(tuán)的演化規(guī)律，對社團(tuán)進(jìn)行更細(xì)致的分析，從而可以起到指導(dǎo)業(yè)務(wù)決策的作用。

Junming Shao等人提出了基于距離動(dòng)力學(xué)的靜態(tài)社團(tuán)發(fā)現(xiàn)算法[9]。算法的核心思想是把目標(biāo)網(wǎng)絡(luò)看作是一個(gè)自適應(yīng)的動(dòng)態(tài)系統(tǒng)，系統(tǒng)內(nèi)的每個(gè)節(jié)點(diǎn)都受它的鄰居的影響。節(jié)點(diǎn)間的距離會(huì)影響交互，而交互會(huì)改變節(jié)點(diǎn)間的距離。這樣的動(dòng)態(tài)交互最終會(huì)形成一個(gè)穩(wěn)定的系統(tǒng)，同屬于一個(gè)社團(tuán)的節(jié)點(diǎn)會(huì)緊密連接，而屬于不同社團(tuán)的節(jié)點(diǎn)會(huì)盡可能遠(yuǎn)離。原文作者利用實(shí)驗(yàn)說明了該算法有著較低的時(shí)間復(fù)雜度以及高質(zhì)量的社團(tuán)發(fā)現(xiàn)效果，值得推廣與應(yīng)用。

對于動(dòng)態(tài)網(wǎng)絡(luò)演化分析有相關(guān)綜述[5,10-11]。Chayant等人提出了識別社團(tuán)結(jié)構(gòu)以及社團(tuán)的動(dòng)態(tài)變化的框架[12]，為以后的研究提供了重要的參考。Derek Greene等人提出了追蹤動(dòng)態(tài)社團(tuán)的模型，并定義了一些社團(tuán)演化事件[13]，對于直觀地理解社團(tuán)的演化有很大幫助。Takaffoli等人提出了元社區(qū)的概念，具有生存期m的元社區(qū)M包含m個(gè)社區(qū)，利用基于社團(tuán)相似度匹配的思想來發(fā)現(xiàn)社團(tuán)演化過程[14]。Bhat等人提出一種基于密度的方法研究社交網(wǎng)絡(luò)動(dòng)態(tài)變化，并利用日志映射來減少相鄰時(shí)間社團(tuán)相似度的比較次數(shù)[15]。

上述的算法大多把社團(tuán)看作一個(gè)整體，僅從整體來考慮社團(tuán)的變化，但是，沒有將社團(tuán)內(nèi)部成員對社團(tuán)演化的影響考慮進(jìn)來。本文首先提出了利用社團(tuán)內(nèi)部與整體兩方面的信息來衡量社團(tuán)的演化，對于社團(tuán)核心成員、社團(tuán)成員相似度、社團(tuán)屬性等一一進(jìn)行加權(quán)，在提高識別關(guān)聯(lián)群準(zhǔn)確率的同時(shí)增加了靈活性。最后，以某銀行真實(shí)業(yè)務(wù)數(shù)據(jù)出發(fā)來探索社團(tuán)在動(dòng)態(tài)網(wǎng)絡(luò)中的變化。由于集團(tuán)企業(yè)組織結(jié)構(gòu)復(fù)雜、財(cái)務(wù)數(shù)據(jù)不易核實(shí)、內(nèi)部關(guān)聯(lián)交易頻繁、連環(huán)擔(dān)保較為普遍，帶來多頭授信、過度授信等問題，對其進(jìn)行的研究具有一定的復(fù)雜性與困難性。本文從銀行業(yè)社團(tuán)固有的一些屬性以及社團(tuán)內(nèi)部的屬性如核心成員、成員組成，來追蹤社團(tuán)的演化序列。應(yīng)用本文提到的算法能準(zhǔn)確地識別出關(guān)聯(lián)群并提取社團(tuán)演化序列，因此本文的方法具有很高的應(yīng)用價(jià)值。

2 社團(tuán)追蹤算法

2.1 相關(guān)定義

為了定量研究網(wǎng)絡(luò)及網(wǎng)絡(luò)特性，一般把網(wǎng)絡(luò)抽象為圖(Graph)，記為G。一個(gè)圖G定義為一個(gè)對(V，E)，即G=(V，E)。V表示圖G中節(jié)點(diǎn)的集合，E表示圖G中邊的集合。近年來，對眾多實(shí)際網(wǎng)絡(luò)的研究發(fā)現(xiàn)，它們存在一個(gè)共同的特征，稱之為網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)。它是指網(wǎng)絡(luò)中的節(jié)點(diǎn)可以分成組，組內(nèi)節(jié)點(diǎn)間的連接比較稠密，組間節(jié)點(diǎn)的連接比較稀疏。一般用C(Community)表示社團(tuán)，如圖1是有著3個(gè)社團(tuán)的小型網(wǎng)絡(luò)。

圖1 一個(gè)小型的具有社團(tuán)結(jié)構(gòu)性質(zhì)的網(wǎng)絡(luò)示意圖Fig.1 Schematic diagram of a small network with community structure

小圓表示節(jié)點(diǎn)，大圓表示社團(tuán)，圖1表示有3個(gè)社團(tuán)的小型網(wǎng)絡(luò)。

本小節(jié)主要介紹一些相關(guān)的定義，以便更好地理解3.2中所提出的算法。

定義1關(guān)聯(lián)群

t、t+1、t+2時(shí)刻分別有4、4、5個(gè)社團(tuán)，A、B、C分別表示演化過程中不同的關(guān)聯(lián)群，由相鄰兩個(gè)時(shí)刻有關(guān)聯(lián)關(guān)系的社團(tuán)構(gòu)成。

定義2網(wǎng)絡(luò)快照和動(dòng)態(tài)網(wǎng)絡(luò)

網(wǎng)絡(luò)隨時(shí)間動(dòng)態(tài)變化，在時(shí)刻t的網(wǎng)絡(luò)稱為t時(shí)刻的網(wǎng)絡(luò)快照，動(dòng)態(tài)網(wǎng)絡(luò)則是一系列網(wǎng)絡(luò)快照的有序序列。在時(shí)刻t的網(wǎng)絡(luò)快照記為St則動(dòng)態(tài)網(wǎng)絡(luò)則可以表示為，1≤t≤T。大多數(shù)研究動(dòng)態(tài)網(wǎng)絡(luò)中的網(wǎng)絡(luò)結(jié)構(gòu)都是將動(dòng)態(tài)網(wǎng)絡(luò)按照時(shí)間劃分為多個(gè)網(wǎng)絡(luò)，將t時(shí)刻的網(wǎng)絡(luò)與t+1的網(wǎng)絡(luò)關(guān)聯(lián)起來再進(jìn)行深入的分析研究。

圖2 關(guān)聯(lián)群的定義示例Fig.2 Example definition of an associated group

定義3社團(tuán)集合

對于每個(gè)網(wǎng)絡(luò)快照S，在時(shí)間t，利用某種靜態(tài)社團(tuán)發(fā)現(xiàn)算法進(jìn)行社團(tuán)挖掘，得到的社團(tuán)集合稱為t時(shí)刻的社團(tuán)集合，簡記為Ct。在1≤t≤T，共有T個(gè)網(wǎng)絡(luò)快照，則相對應(yīng)有T個(gè)社團(tuán)集合。若根據(jù)靜態(tài)社團(tuán)發(fā)現(xiàn)在St上挖掘出n個(gè)社團(tuán)，t時(shí)刻的n個(gè)社團(tuán)可表示為Ct={Ct1,Ct2,…,Ctn}。

定義4社團(tuán)演化序列

在動(dòng)態(tài)網(wǎng)絡(luò)中，社團(tuán)從t=1時(shí)刻(或從產(chǎn)生時(shí)刻)到t=T時(shí)刻(或消失時(shí)刻)的社團(tuán)動(dòng)態(tài)變化的序列(其中1≤t≤T)，稱為社團(tuán)演化序列，簡記為Seq。社團(tuán)演化序列的獲取方法可以在3.2中關(guān)聯(lián)群追蹤算法中看到。圖3是一種可能的社團(tuán)演化情景。

圖3 一種可能的社團(tuán)演化情景Fig.3 A possible scenario of community evolution

Ct為t時(shí)刻St中社團(tuán)的集合。C2={C21,C22,C23,C24}，C3={C31,C32,C33,C34,C35}，C4={C41,C42,C43,C44}。Seqn表示追蹤得到的社團(tuán)序列，上圖中有5個(gè)Seq，其中Seq1=(C11,C21,C31,C41)，Seq2=(C22,C32)，Seq3=(C12,C13,C23,C33,C43)，Seq4=(C14,C24,C34,C44)，Seq5=(C14,C24,C35)。

定義5關(guān)鍵演化事件

關(guān)鍵演化事件是指在社團(tuán)隨時(shí)間變化的過程中社團(tuán)自身出現(xiàn)的一些較為明顯的變化行為。關(guān)注關(guān)鍵演化事件，對于研究關(guān)聯(lián)群的演化有著重要作用。除了社團(tuán)不變這一極少發(fā)生的特殊事件外，關(guān)鍵演化事件一般有以下6類事件：

1)社團(tuán)膨脹：社團(tuán)演化到T時(shí)刻，在T時(shí)刻的規(guī)模明顯大于它上一時(shí)刻的規(guī)模并且增大的程度大于10%時(shí)，即認(rèn)為社團(tuán)發(fā)生了膨脹，記為E。如圖3中C31→C41。

2)社團(tuán)收縮：社團(tuán)演化到T時(shí)刻，在T時(shí)刻的規(guī)模明顯小于它上一時(shí)刻的規(guī)模并且減小的程度大于10%時(shí)，即認(rèn)為社團(tuán)發(fā)生了收縮，記為R。如圖3中C22→C32。

3)社團(tuán)合并：T時(shí)刻的2個(gè)或多個(gè)社團(tuán)在T+1時(shí)刻合并為一個(gè)社團(tuán)，定義為社團(tuán)的合并，記為M。如圖3中的C12、C13→C23。

4)社團(tuán)分裂：T時(shí)刻的1個(gè)社團(tuán)在T+1時(shí)刻分裂為2個(gè)或多個(gè)社團(tuán)，定義為社團(tuán)的分裂，記為S。如圖3中的C24→C34、C35。

5)社團(tuán)新生：社團(tuán)演化序列的起點(diǎn)均為新生社團(tuán)。特別地，在T=1時(shí)刻的社團(tuán)都為新生社團(tuán)。

6)社團(tuán)死亡：T時(shí)刻的社團(tuán)演化到T+1時(shí)刻不再存在，定義為社團(tuán)死亡。如圖3中的C32發(fā)生了社團(tuán)死亡事件。

2.2 社團(tuán)追蹤算法

由上3.1節(jié)定義可知，關(guān)聯(lián)群是相鄰時(shí)刻存在關(guān)聯(lián)關(guān)系的社團(tuán)或群。如何確定其關(guān)聯(lián)關(guān)系是本節(jié)的重點(diǎn)。每個(gè)社團(tuán)都有一些特性，傳統(tǒng)方式衡量兩個(gè)社團(tuán)間的相關(guān)關(guān)系如演化相似性通常以局部特性或整體特性來衡量，本節(jié)則以加權(quán)的綜合特性來衡量社團(tuán)間的演化相似度，當(dāng)演化相似度大于一定閾值，則定義為兩者存在關(guān)聯(lián)關(guān)系，也即形成關(guān)聯(lián)群；反之，兩者不能形成關(guān)聯(lián)群。在形成關(guān)聯(lián)群的過程中，會(huì)有一些關(guān)鍵的演化事件發(fā)生，本算法不僅能追蹤到關(guān)聯(lián)群，也能觀測到關(guān)鍵演化事件。

2.2.1 核心成員

本文中所研究的對象是社團(tuán)，社團(tuán)是由社團(tuán)成員所組成。以往研究社團(tuán)時(shí)，大都把社團(tuán)成員同等看待，本文將社團(tuán)成員分為核心成員與非核心成員兩類。在一個(gè)社團(tuán)中，核心成員往往對整個(gè)社團(tuán)的存在或消亡起著決定性的作用。

核心成員的識別首先要尋找到該社團(tuán)成員的特征屬性，這些所選擇的特征屬性能較明顯的反映每個(gè)成員的基本性質(zhì)，比如存款數(shù)量、借款金額等等。本文利用專家評分法[19]，對社團(tuán)中的每個(gè)成員的綜合評分進(jìn)行量化，所選取的綜合評分最高的節(jié)點(diǎn)為社團(tuán)核心成員。該核心成員的特點(diǎn)是基于所選擇的特征屬性，按照該方法計(jì)算的綜合得分最高。社團(tuán)成員的特征經(jīng)過特征提取后得到特征集合，如：X=[x1,x2,…,xn]。利用選定的專家評分表，從而得到核心成員的綜合評價(jià)得分。

(1)

其中a、b分別為t和t+1時(shí)刻的某一社團(tuán)，KMa表示社團(tuán)a的核心成員。則式(1)表示社團(tuán)a中的核心成員是否在社團(tuán)b中。如果在，則KernelMember(a,b)為1，若不在，則KernelMember(a,b)為0。

2.2.2 成員相似度

社團(tuán)的成員是社團(tuán)的重要屬性，也是社團(tuán)演化中需要著重關(guān)注的屬性，如社團(tuán)的膨脹、萎縮都根據(jù)社團(tuán)成員規(guī)模來衡量。而兩個(gè)社團(tuán)成員之間的相似度，往往能反映后一個(gè)社團(tuán)是否由前一個(gè)社團(tuán)演化而來，相似度越大，越有把握確定兩者之間的演化關(guān)系，越可能形成關(guān)聯(lián)群。社團(tuán)成員的相似度用Jaccard相似系數(shù)[17]來衡量。

(2)

其中，Member(a)指社團(tuán)a的成員，Member(b)指社團(tuán)b的成員。分子部分取兩者共有的成員個(gè)數(shù)，即a與b交集的元素個(gè)數(shù)；分母部分取a與b并集的元素個(gè)數(shù)。

2.2.3 社團(tuán)相似度

社團(tuán)相似指在相鄰的兩個(gè)時(shí)間截面，T時(shí)刻中的社團(tuán)與T+1時(shí)刻社團(tuán)的相似程度。確定社團(tuán)演化序列時(shí)，需要計(jì)算兩個(gè)社團(tuán)之間的相似程度。樣本的線性相關(guān)性會(huì)干擾對樣本點(diǎn)相似性的度量，而利用余弦相似度度量樣本點(diǎn)的相似程度可以有效地避免樣本點(diǎn)線性相關(guān)的干擾。利用基于夾角余弦的相似度計(jì)算方法是進(jìn)行社團(tuán)分析的常用方法之一。社團(tuán)a，b的余弦相似度[18]計(jì)算如式(3)：

(3)

其中，A為關(guān)聯(lián)群a的屬性構(gòu)成的屬性向量，同理，B是b的屬性向量。

2.2.4 演化相似度

前后兩個(gè)社團(tuán)之間是否形成關(guān)聯(lián)群與上述核心成員、成員相似度、社團(tuán)相似度都有著不可分割的關(guān)系。最終演化相似度可以用式(4)來衡量。

(4)

其中，α，β，γ是超參數(shù)，取值范圍為[0，1]，控制某一個(gè)分量的重要程度，且α+β+β=1。λ是拉普拉斯平滑系數(shù)，為了平滑KernelMember(a,b)為0的情況，本文取值為1。KernelMember(a,b)指a中的核心成員是否仍在b中；Jaccard(a,b)表示社團(tuán)a與社團(tuán)b中個(gè)體成員的相似度；Cos(a,b)表示a，b兩個(gè)社團(tuán)屬性之間的余弦相似度。Esim(a,b)指兩個(gè)社團(tuán)之間的演化相似度。當(dāng)Esim(a,b)>θ(某一閾值)，則a與b形成關(guān)聯(lián)群，并將b加入到a的演化序列中。

2.2.5 社團(tuán)追蹤算法

對于如何追蹤社團(tuán)演化序列的問題，本文提出了一種“多部圖”匹配的方法。多部圖是一種分層的圖，每一層表示一個(gè)時(shí)刻的社團(tuán)集合，層中的一個(gè)節(jié)點(diǎn)表示一個(gè)社團(tuán)。多部圖也可以看作多個(gè)二部圖的集合，相鄰時(shí)刻的社團(tuán)集合作為二部圖的兩個(gè)子部分，圖4是一個(gè)簡單的多部圖示例。

圖4 簡單多部圖示例Fig.4 Simple multi-image example

t、t+1、t+2時(shí)刻的社團(tuán)集合中的社團(tuán)連接形成的簡單多部圖。每個(gè)節(jié)點(diǎn)表示一個(gè)社團(tuán)，每一層表示一個(gè)時(shí)刻的社團(tuán)集合，上圖為3個(gè)時(shí)刻的社團(tuán)集合形成的3部圖。

利用多部圖進(jìn)行社團(tuán)追蹤，生成演化序列的方法如下：

1)初始時(shí)，不同層之間進(jìn)行全連接，所有邊權(quán)重賦值為一個(gè)極小的值。

2)利用式(4)中的演化相似度公式重新更新權(quán)重。

3)刪除邊權(quán)重小于閾值θ的邊。

4)提取圖中所有的路徑，即為演化序列。

關(guān)聯(lián)群表示有關(guān)聯(lián)關(guān)系的社團(tuán)集合，本節(jié)針對關(guān)聯(lián)關(guān)系進(jìn)行了深入分析。利用綜合加權(quán)的演化相似度來衡量社團(tuán)之間的關(guān)聯(lián)關(guān)系。不同領(lǐng)域關(guān)注的影響關(guān)聯(lián)關(guān)系的因素不同，利用權(quán)重可以方便地調(diào)節(jié)各因素的比重，具有較好的靈活性。提出多部圖的思想對演化序列進(jìn)行提取，是社團(tuán)序列追蹤的一種新方法。綜合加權(quán)的演化相似度和多部圖兩者結(jié)合在一起，能有效且準(zhǔn)確地進(jìn)行社團(tuán)追蹤。

社團(tuán)追蹤算法描述如下：

輸入：網(wǎng)絡(luò)快照、α、β、γ、θ

輸出：社團(tuán)演化序列Seqs

1) for 1<=t<=T:

Ct( 社團(tuán)挖掘(St)

end for;

2) Order(Ct)；

3) 每個(gè)Ct對應(yīng)多部圖一個(gè)子圖；

4) 多部圖中的相鄰兩層節(jié)點(diǎn)進(jìn)行全連接；

5) 初始化邊權(quán)重:

for edge inG:

weightedge( 0

end for

6) forCainCt：

forCbinCt+1：

計(jì)算核心成員相似度KernelMember(a,b);

計(jì)算成員相似度Jaccard(a,b)

計(jì)算社團(tuán)屬性相似度Cos(a,b)；

計(jì)算演化相似度Esim(a,b)

weightedge(Esmin(a,b)

end for

7) for edge inG:

ifweightedge<θ：

將邊刪除

end if

end for

8) 提取剩余多部圖中的有向路徑，得到最終的演化序列Seqs。

3 實(shí)驗(yàn)驗(yàn)證

基于上文提出的綜合加權(quán)的演化相似度以及社團(tuán)追蹤算法，利用多部圖進(jìn)行社團(tuán)的追蹤。本節(jié)主要闡述了實(shí)驗(yàn)流程，并對使用的數(shù)據(jù)以及數(shù)據(jù)的預(yù)處理做了簡單介紹，最終利用預(yù)處理之后的數(shù)據(jù)進(jìn)行社團(tuán)追蹤算法的驗(yàn)證分析。

3.1 實(shí)驗(yàn)流程

利用已有數(shù)據(jù)，結(jié)合上述所提出的社團(tuán)追蹤算法以及多部圖思想，進(jìn)行社團(tuán)演化序列的提取。根據(jù)偽代碼以及每一步所需數(shù)據(jù)，設(shè)計(jì)實(shí)驗(yàn)流程如圖5所示。

圖5 實(shí)驗(yàn)流程圖Fig.5 Experimental flow chart

前期是數(shù)據(jù)準(zhǔn)備階段，當(dāng)數(shù)據(jù)準(zhǔn)備完成后便可利用3.2節(jié)所提出的算法便可進(jìn)行社團(tuán)的追蹤。在進(jìn)行社團(tuán)追蹤的同時(shí)，還可觀察到各種演化事件隨超參數(shù)的變化而變化。社團(tuán)追蹤算法的具體步驟如下：

令網(wǎng)絡(luò)快照表示為St,1≤t≤T.

步驟1 利用靜態(tài)社團(tuán)發(fā)現(xiàn)算法[9],挖掘出每個(gè)網(wǎng)絡(luò)快照中St的社團(tuán)。

步驟2 對于步驟1挖掘出的社團(tuán)，按照時(shí)間順序排列，形成社團(tuán)集合序列。

步驟3 每個(gè)時(shí)間截面上社團(tuán)集合對應(yīng)多部圖的一個(gè)子圖。

步驟4 多部圖的每一層的每一個(gè)節(jié)點(diǎn)與下一層進(jìn)行全連接，形成全連接的有向多部圖。

步驟5 對于多部圖中有向邊權(quán)重初始化為0。

步驟6 利用式(4)計(jì)算每條邊的演化相似度，并將有向邊權(quán)重更新為演化相似度。

步驟7 刪除多部圖中有向邊的權(quán)重小于閾值θ的邊。

步驟8 對于多部圖的剩余部分，提取圖中的路徑，形成演化序列。

3.2 數(shù)據(jù)準(zhǔn)備

本實(shí)驗(yàn)數(shù)據(jù)來源于某金融機(jī)構(gòu)2011年1月—2011年12月一整年的數(shù)據(jù)，數(shù)據(jù)已經(jīng)過脫敏、匿名化處理。利用靜態(tài)社團(tuán)發(fā)現(xiàn)算法得到的結(jié)果，每月大約有4萬左右社團(tuán)。各月社團(tuán)數(shù)量統(tǒng)計(jì)圖如圖6所示。

圖6 各月社團(tuán)數(shù)量統(tǒng)計(jì)Fig.6 Statistics on the number of associations in each month

由圖6可知，該金融機(jī)構(gòu)每個(gè)月社團(tuán)數(shù)量在不斷地增加。由于其用戶數(shù)在不斷地增長，基本符合實(shí)際情況。本文主要研究的是成員數(shù)大于3的社團(tuán)，利用這些數(shù)據(jù)對上述算法進(jìn)行實(shí)驗(yàn)驗(yàn)證。

1)社團(tuán)發(fā)現(xiàn)與社團(tuán)過濾。分別輸入2011年1月—2011年12月12個(gè)月的網(wǎng)絡(luò)快照，根據(jù)靜態(tài)社團(tuán)發(fā)現(xiàn)算法[9]來進(jìn)行社團(tuán)的識別與檢測，再過濾掉社團(tuán)成員數(shù)量不大于3的社團(tuán)，得到12個(gè)社團(tuán)集合。

2)信息提取。對12個(gè)社團(tuán)集合進(jìn)行信息提取，得到了以下幾個(gè)表的信息。其中社團(tuán)信息表中成員的詳細(xì)信息包含在成員信息表中；成員信息表中每個(gè)成員的屬性包含在成員屬性表中，即成員信息表是社團(tuán)信息表中具體成員的展開，成員屬性表是成員信息表中成員的屬性。

表1顯示的是2011年1月份部分社團(tuán)的信息，主要包括社團(tuán)群號、時(shí)間、社團(tuán)成員數(shù)以及其他屬性。

表1 2011年01月社團(tuán)信息表Tab.1 Information sheet of associations for January 2011

表2是2011年1月份的3個(gè)社團(tuán)，主要包括社團(tuán)ID、時(shí)間、社團(tuán)成員ID。關(guān)聯(lián)群ID分別為′201101-1-152318-1299165686073′，′201101-1-152332-1299165686088′，′201101-1-152333-1299165686089′。每個(gè)社團(tuán)包含的成員數(shù)量分別有5個(gè)，3個(gè)，3個(gè)。

表2 2011年1月成員信息表Tab.2 Information sheet of member for January 2011

每個(gè)成員都有其自身的屬性，表3展示了社團(tuán)成員的屬性。

表3 成員屬性表Tab.3 Information sheet of member attribute

表4 核心成員表Tab.4 Information sheet of core member

利用前文提到的專家評分法，通過計(jì)算從而確定每個(gè)社團(tuán)的核心成員。社團(tuán)與核心成員表如表4所示。

3.3 實(shí)驗(yàn)分析

其中，B為社團(tuán)新生(Birth)、D為社團(tuán)死亡(Death)、M為社團(tuán)合并(Merge)、S為社團(tuán)分裂(Split)、E為社團(tuán)膨脹(Expand)、R為社團(tuán)收縮(shRink)。圖7 1-12月份相鄰兩個(gè)月之間社團(tuán)演化事件隨α的變化統(tǒng)計(jì)Fig.7 Statistical changes of association evolution events with α between adjacent months in January-December

圖7表示，當(dāng)α從0.1到0.9變化時(shí)，相鄰兩個(gè)月之間發(fā)生的6類關(guān)鍵社團(tuán)演化事件的統(tǒng)計(jì)。共有11個(gè)圖，分別表示1-2月，2-3月，…，11-12月關(guān)鍵演化事件隨α的變化。相鄰兩個(gè)月社團(tuán)演化事件隨β、γ的變化與圖7類似。

結(jié)合銀行已有的真實(shí)數(shù)據(jù)，發(fā)現(xiàn)當(dāng)α為0.7-0.8左右，本算法所追蹤到的社團(tuán)演化與已有的社團(tuán)演化相似度最大，說明核心成員對最終結(jié)果影響較大。分析原因是因?yàn)樵阢y行業(yè)中，核心成員多為龍頭企業(yè)，而這種個(gè)體有較大概率影響到他所在的社團(tuán)。所以，在本文所提出的算法中核心成員的權(quán)重較大。當(dāng)α=0.70，β=γ=0.15，綜合加權(quán)的演化相似度所識別的關(guān)聯(lián)群的準(zhǔn)確率分別與非加權(quán)的核心成員、成員相似度、社團(tuán)屬性相似度的關(guān)聯(lián)群識別準(zhǔn)確率如圖8所示。

由圖8可以看出，綜合加權(quán)識別準(zhǔn)確率平均在86%左右，達(dá)到了較高的識別率。只用核心成員識別關(guān)聯(lián)群的準(zhǔn)確率高于其他兩個(gè)低于綜合加權(quán)的識別率，說明核心成員影響較大，但也有其他因素影響，如成員相似度。社團(tuán)的屬性識別率對于關(guān)聯(lián)群的識別效果最差，且識別結(jié)果波動(dòng)較大，說明在銀行業(yè)中識別關(guān)聯(lián)群此類指標(biāo)重要程度最低。修改各指標(biāo)中的超參數(shù)便可應(yīng)用于其他的領(lǐng)域，因此，本文所提出的算法具有較強(qiáng)的靈活性。表5是當(dāng)α取0.7時(shí)，β=γ=0.15時(shí)，從1月份到12月份一直存在的一些社團(tuán)所構(gòu)成的演化序列。

圖8 關(guān)聯(lián)群識別準(zhǔn)確率Fig.8 Accuracy of association group identification

表5 1-12月份的一直存在社團(tuán)序列Tab.5 The ever-presenting community sequence from January to December

4 結(jié)論

本文提出了一種動(dòng)態(tài)社團(tuán)追蹤算法，通過對社團(tuán)相似度、成員相似度以及核心成員相似的加權(quán)來衡量相鄰時(shí)刻的社團(tuán)相似度。隨后引入多部圖，以相似度為邊權(quán)重，與超參數(shù)θ進(jìn)行比較，來確定邊是否保留。最終提取多部圖中的有向路徑，從而得到演化序列。并以實(shí)驗(yàn)證明了該方法的有效性與可行性，實(shí)驗(yàn)結(jié)果也說明了本文的算法具有較強(qiáng)的靈活性，當(dāng)核心成員特別重要時(shí)，可以將核心成員的權(quán)重加大，而更關(guān)注社團(tuán)的整體屬性時(shí)，可以將社團(tuán)的屬性權(quán)重增大。缺點(diǎn)是當(dāng)數(shù)據(jù)規(guī)模龐大時(shí)，由于O(N2)的復(fù)雜度，計(jì)算開銷會(huì)很大，這是以后改進(jìn)的重點(diǎn)。利用機(jī)器學(xué)習(xí)方法進(jìn)行超參數(shù)的自動(dòng)調(diào)整，也是進(jìn)一步的研究方向。

在真實(shí)網(wǎng)絡(luò)中，社團(tuán)結(jié)構(gòu)大量存在，本文是以銀行業(yè)務(wù)數(shù)據(jù)進(jìn)行了驗(yàn)證。也可以把這種追蹤算法進(jìn)行推廣，應(yīng)用在其他領(lǐng)域，如社交網(wǎng)絡(luò)。所提出的社團(tuán)追蹤算法還可以進(jìn)行反向推廣，如可用于社團(tuán)循跡。