基于關(guān)聯(lián)群演化相似度的社團追蹤算法

徐 兵，趙亞偉，徐楊遠翔

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

0 引言

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

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

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

1 相關(guān)工作

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

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

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

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

2 社團追蹤算法

2.1 相關(guān)定義

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

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

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

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

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

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

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

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

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

定義3社團集合

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

定義4社團演化序列

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

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

Ct為t時刻St中社團的集合。C2={C21,C22,C23,C24}，C3={C31,C32,C33,C34,C35}，C4={C41,C42,C43,C44}。Seqn表示追蹤得到的社團序列，上圖中有5個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)鍵演化事件是指在社團隨時間變化的過程中社團自身出現(xiàn)的一些較為明顯的變化行為。關(guān)注關(guān)鍵演化事件，對于研究關(guān)聯(lián)群的演化有著重要作用。除了社團不變這一極少發(fā)生的特殊事件外，關(guān)鍵演化事件一般有以下6類事件：

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

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

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

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

5)社團新生：社團演化序列的起點均為新生社團。特別地，在T=1時刻的社團都為新生社團。

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

2.2 社團追蹤算法

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

2.2.1 核心成員

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

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

(1)

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

2.2.2 成員相似度

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

(2)

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

2.2.3 社團相似度

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

(3)

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

2.2.4 演化相似度

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

(4)

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

2.2.5 社團追蹤算法

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

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

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

利用多部圖進行社團追蹤，生成演化序列的方法如下：

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

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

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

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

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

社團追蹤算法描述如下：

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

輸出：社團演化序列Seqs

1) for 1<=t<=T:

Ct( 社團挖掘(St)

end for;

2) Order(Ct)；

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

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

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

for edge inG:

weightedge( 0

end for

6) forCainCt：

forCbinCt+1：

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

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

計算社團屬性相似度Cos(a,b)；

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

weightedge(Esmin(a,b)

end for

7) for edge inG:

ifweightedge<θ：

將邊刪除

end if

end for

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

3 實驗驗證

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

3.1 實驗流程

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

圖5 實驗流程圖Fig.5 Experimental flow chart

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

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

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

步驟2 對于步驟1挖掘出的社團，按照時間順序排列，形成社團集合序列。

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

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

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

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

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

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

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

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

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

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

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

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

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

表1 2011年01月社團信息表Tab.1 Information sheet of associations for January 2011

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

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

每個成員都有其自身的屬性，表3展示了社團成員的屬性。

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

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

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

3.3 實驗分析

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

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

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

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

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

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

4 結(jié)論

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

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