基于異同性的社區(qū)演化分類方法

劉業(yè)強,王魯,楊圣彬,劉亞瓊

基于異同性的社區(qū)演化分類方法

劉業(yè)強1,王魯1,楊圣彬2*,劉亞瓊2

1. 山東農(nóng)業(yè)大學信息科學與工程學院, 山東 泰安 271018 2. 山東農(nóng)業(yè)大學網(wǎng)絡信息技術中心, 山東 泰安 271018

動態(tài)網(wǎng)絡中的社區(qū)演化分析是目前的研究熱點之一，其在輿論控制、網(wǎng)絡營銷和個性化推薦服務等方面有著重要作用。提出一種基于節(jié)點重要性評價指標的差值吸收核心節(jié)點檢測算法，首先計算各節(jié)點的相對權重值，進而劃分核心節(jié)點，并以此為基礎優(yōu)化差異性公式，提出一種異同性社區(qū)演化分類模型，從相似性和差異性兩方面對演化類型進行劃分。將提出的分類模型與GED及SGCI在HEP-TH和波蘭政治博客圈數(shù)據(jù)集上進行比較，實驗結果表明，提出的分類模型在整體上優(yōu)于GED及SGCI，尤其在Forming和Dissolving事件的檢測時，可以做到對小社區(qū)敏感，能檢測到小社區(qū)的多種演化類型。

聚類系數(shù); 核心節(jié)點檢測; 社區(qū)演化分類模型

社交網(wǎng)絡被定義為以圖形表示的信息網(wǎng)絡，可以描述個體之間的交互行為。在社交網(wǎng)絡中，個體由網(wǎng)絡中的一個節(jié)點來表示，邊則表示個體之間的交互作用或者個體間存在的某種關系。例如，在因特網(wǎng)中人與人之間的聯(lián)系，即思想、信息的交換可以被建模為一個社交網(wǎng)絡；科學家合作網(wǎng)中，節(jié)點表示作者，兩作者合作產(chǎn)生文章即表示一條邊。社區(qū)結構是社交網(wǎng)絡的特性，即同一社區(qū)內(nèi)的節(jié)點聯(lián)系較為緊密，社區(qū)間的節(jié)點聯(lián)系較為松散。同一社區(qū)內(nèi)的成員通常有著某一共性，例如興趣愛好、研究領域和文化交流等。當有新節(jié)點加入網(wǎng)絡，現(xiàn)有節(jié)點離開網(wǎng)絡，現(xiàn)有節(jié)點與其他節(jié)點建立新聯(lián)系或現(xiàn)有節(jié)點與其他節(jié)點的聯(lián)系消失時，社交網(wǎng)絡會產(chǎn)生演化行為，變化的網(wǎng)絡即為動態(tài)社交網(wǎng)絡[1]。動態(tài)社交網(wǎng)絡社區(qū)演化分析以動態(tài)社區(qū)發(fā)現(xiàn)的結果為基礎分析社區(qū)變化，如生長、分裂、收縮和消失等。社區(qū)演化分析可以發(fā)現(xiàn)網(wǎng)絡潛在的演化規(guī)律，推導個體之間的交互模式，在定向營銷和廣告、輿論控制、蛋白質(zhì)網(wǎng)絡、傳染病控制等方面有著廣泛的應用[2]。

對社區(qū)演化的分析通常分為兩方面，一是判斷不同時序的社區(qū)是否具有演化關系，常用的方法是基于相似度的演化分析和基于核心節(jié)點的演化分析；二是判定演化類型，需要建立社區(qū)演化分類模型來判定[3]?；谙嗨贫鹊难莼治鏊惴ㄒ韵噜弮蓚€時間片內(nèi)社區(qū)之間的相似性為標準來判斷社區(qū)的演化事件，社區(qū)相似性多以Jaccard系數(shù)為度量，但此方法忽略了網(wǎng)絡的拓撲結構信息，同時閾值的選擇也有很大的不確定性；基于核心節(jié)點的演化分析利用具有穩(wěn)定性的核心節(jié)點來代表整個社區(qū)，分析社區(qū)的演化行為。Bhat等[4]提出基于密度的核心節(jié)點演變分析方法，根據(jù)節(jié)點在一定鄰域范圍內(nèi)的密度來選擇網(wǎng)絡中的核心節(jié)點，并且在每個時間片更新增量節(jié)點的屬性；Yin等[5]提出基于引力關系重構的核心節(jié)點演化分析算法，將引力的概念引入社交網(wǎng)絡進行社區(qū)發(fā)現(xiàn)；Dhouioui等[6]提出了一個識別演化事件的框架，該框架要求在每個社區(qū)范圍內(nèi)都找出核心節(jié)點，并且將邊緣度更小的節(jié)點加入核心節(jié)點集合，然后根據(jù)核心節(jié)點變化識別演化事件。社區(qū)演化分類模型可以用來判定演化類型。2012年，Bródka等[7]提出了演化模型GED，將社區(qū)演化分類為七種類型，包含了社區(qū)從生成到消失的整個生命周期，并首次增加了節(jié)點重要度的概念。同年，Gliwa等[8]提出了一種基于穩(wěn)定聚類的演化分析方法SGCI，提出了與GED不同的演化分類模型，認為噪聲聚類對演化結果沒有實質(zhì)影響。

本文提出的差值吸收核心節(jié)點檢測算法基于節(jié)點重要性評價指標p[9]，該指標由節(jié)點鄰居信息以及集聚系數(shù)計算得出，只需考慮節(jié)點的鄰居個數(shù)以及其鄰居之間的連接緊密程度等局部信息，因此對大規(guī)模網(wǎng)絡同樣可以進行有效分析。該算法以p為基礎，將有邊連接的兩節(jié)點進行一一比對，p值較大的節(jié)點其權重值增加，p值較小的節(jié)點其權重值減少。由此方法確定核心節(jié)點集，改進差異性公式，并結合現(xiàn)有的相似性公式，提出一種異同性社區(qū)演化分類模型(the classification model of community evolution based on similarities and differences, SDCE)，從相似性和差異性兩方面判定演化類型。

1 相關研究

1.1 節(jié)點重要性評價指標

節(jié)點重要性評價指標p綜合考慮節(jié)點的鄰居個數(shù)以及其鄰居之間的連接緊密程度，只考慮網(wǎng)絡局部信息，因此算法時間復雜度較低，其計算式為：

式中：f為節(jié)點自身度與其鄰居度之和, 其計算式表示為：

式中：k表示節(jié)點的度，F表示節(jié)點的鄰居節(jié)點集合。g計算式表示為：

式中：c為節(jié)點的聚類系數(shù)，g是對c/f的歸一化處理。

1.2 差異性公式

差異性公式由Zygmunt等[10]提出，算法共分兩步，首先基于PageRank算法計算節(jié)點的重要性排名，之后以共有節(jié)點的變化幅度反映社區(qū)的變化幅度，其計算式為：

式中：=indexG()=indexG()，indexG()表示節(jié)點在G中的重要度排名；表示節(jié)點重要度，基于PageRank及歷史社區(qū)信息計算得出。

1.3 相似性公式

相似性公式以Jaccard相似度公式為基礎進行改進，通過節(jié)點對社區(qū)進行相似性判斷[11]，其計算式為：

1.4 GED演化分類模型

GED以Jaccard相似度評估公式為基礎，增加了節(jié)點重要度的概念，將其作為判定標準，對社區(qū)間的相似度進行判定，進而劃分事件類型。演化類型分為七種，以改進的相似度公式I(G,G)對演化進行判定，其中：

每種演化類型判別如下：

[1] Forming(生成)：對于2:(12)<10% and(G,G)<10%，其中G∈T，G∈T1，此時社區(qū)G生成。

[2] Continuing(持續(xù))：(12)≥and(21)≥and12.

[3] Growing(生長)：(12)≥and(21)≥and12OR(12)≥and(21)T1中的一個社區(qū)匹配成功。

[4] Shrinking(萎縮)：(12)≥and(21)≥and12OR(12)<α and(21)≥and12，且2只能與前一時間窗口T中的一個社區(qū)匹配成功。

[5] Merging(合并)：(12)≥α and(21)G與下一時間窗口T1中的多個社區(qū)匹配成功。

[6] Splitting(分裂)：(12)T中的多個社區(qū)匹配成功。

[7] Dissolving(消失)：對于1:(12)<10% and(21)<10%，其中1∈T，2∈T1，此時社區(qū)1消失。

2 算法描述

2.1 差值吸收核心節(jié)點檢測算法

通常，一個節(jié)點的權重越高，它在社區(qū)中的影響力就越大，對社區(qū)相似性檢驗以及演化類型的判斷起著重要作用。社區(qū)中核心節(jié)點的選擇是關鍵部分，提出的差值吸收核心節(jié)點檢測算法，以節(jié)點重要性評價指標p為基礎，對有邊連接的兩個節(jié)點進行一一比較，依據(jù)比較結果得到相對權重值，確定核心節(jié)點。算法分為三步：第一步，計算每個節(jié)點的p值；第二步，初始化節(jié)點權重值CoC(N)為0，對有邊連接的兩節(jié)點進行一一比較，p值較大的節(jié)點，其CoC(N)值增加；p值較小的節(jié)點，其CoC(N)值減少。第三步，遍歷節(jié)點，選取CoC(N)值大于0的節(jié)點即核心節(jié)點，放入核心節(jié)點集并返回。其中表示兩節(jié)點p差值的絕對值。算法第一步只考慮節(jié)點及其鄰居關系而非整個社區(qū)，第二步只需遍歷邊集，因此算法時間復雜度較低，對大社區(qū)同樣可以進行有效分析。

算法1差值吸收核心節(jié)點檢測算法 輸入：節(jié)點集V，邊集E 輸出：核心節(jié)點集CoreNodeSet 1. for every node vi∈V do 2. calculate the pi by (1); 3. end for 4. CoC(Ni)=0, i∈[1, n]; 5. for edge e∈E do 6. DV=|pi - pj|; 7. Ni,Njare nodes connected with e; 8. if pi > pj then 9. CoC(Ni) = CoC(Ni) + DV; CoC(Nj) = CoC(Nj)－DV; 10. else if pi < pj then 11. CoC(Ni) = CoC(Ni)－DV; CoC(Nj) = CoC(Nj) + DV; 12. end if 13. end for 14. for every CoC(Ni) do 15. if CoC(Ni) > 0 then 16. Input code vi into CoreNodeSet; 17. end if 18. end for 19. return CoreNodeSet

文獻[6]中給出了10個節(jié)點的網(wǎng)絡圖（圖1），并計算出了各節(jié)點的p值。依據(jù)該核心節(jié)點檢測算法可得各節(jié)點的CoC(N)值，如表1所示。由結果可知，節(jié)點2,3,4,6,8的CoC(N)值大于0，因此核心節(jié)點集為{2,3,4,6,8}。下文將以得到的核心節(jié)點集和CoC(N)值為基礎，分別從節(jié)點的選擇、節(jié)點的影響力值等方面改進差異性公式，對社區(qū)的差異性進行判斷。

圖1 10個節(jié)點的網(wǎng)絡圖

Fig.1 Network diagram of 10 nodes

表1 各節(jié)點CoC(Ni)值

2.2 基于核心節(jié)點集的差異性公式

社區(qū)演化評估公式也稱為社區(qū)相似度評估公式，通過比較兩個社區(qū)的一些特征來評估兩個社區(qū)是否足夠相似。為了挖掘演化關系，需要將兩個相鄰時間窗的社區(qū)進行一一比對，判斷其是否相似。區(qū)分于GED等，提出的異同性演化分類模型從相似性和差異性兩方面進行判定，相似性以jaccard相似度為基礎，從宏觀層面體現(xiàn)了社區(qū)拓撲結構的共性；差異性以核心節(jié)點為基礎，從微觀層面體現(xiàn)了核心節(jié)點的變化對社區(qū)的影響。其中，相似性公式為式(5)，差異性公式在式(4)的基礎上進行優(yōu)化，表示為：

其中主要有三方面的改進，一是節(jié)點的選擇，原文中代表所有節(jié)點，式(7)將其優(yōu)化為核心節(jié)點集中的節(jié)點，以體現(xiàn)核心節(jié)點對社區(qū)演化的主導作用；二是將式(4)中的影響力值()替換為由評價指標p計算得出的節(jié)點權重值()；三是在計算過程中發(fā)現(xiàn)，由于分母為G∪G，導致會出現(xiàn)核心節(jié)點只存在于G或只存在于G的情況，此時的計算是無意義的，因此改為G∩G，可有效降低算法時間復雜度。

2.3 異同性社區(qū)演化分類模型

提出的SDCE模型以現(xiàn)有的相似性公式和改進的差異性公式為判定依據(jù)，從社區(qū)間的相似性和差異性兩方面對社區(qū)演化類型進行判定。按照GED分類模型對異同性分類模型進行分類，共分為Continuing, Shrinking, Growing, Splitting, Merging, Dissolving和Forming七種類型，分類標準如下：

[1] Forming(生成)：對于前一時間窗口1的任一社區(qū)，社區(qū)與都不滿足≤且≥；

[2] Continue(持續(xù))：在后一時間窗口1中只能找到一個社區(qū)與社區(qū)滿足≤且≥且；

[3] Growing(生長)：在后一時間窗口1中只能找到一個社區(qū)與社區(qū)滿足≤且≥且；

[4] Shrinking(萎縮)：在后一時間窗口t+1中只能找到一個社區(qū)與社區(qū)滿足≤且≥且；

[5] Merging(合并)：在前一時間窗口1中能找到大于等于2個社區(qū)，且任一社區(qū)與社區(qū)都滿足≤且≥且；

[6] Splitting(分裂)：在后一時間窗口1中能找到大于等于2個社區(qū)，且任一社區(qū)與社區(qū)都滿足≤且≥且；

[7] Dissolving(消失)：對于后一時間窗口1中的任一社區(qū)，社區(qū)與都不滿足≤且≥；

本節(jié)首先提出差值吸收核心節(jié)點檢測算法，得到社區(qū)核心節(jié)點集和各節(jié)點的相對權重值(N)，以此為基礎改進差異性公式，并將改進的差異性公式應用于演化類型的判定標準中，對演化類型進行分類。

3 結果分析

為了驗證異同性演化分類模型SDCE的有效性，將此模型與GED及SGCI在測試數(shù)據(jù)集HEP-TH和波蘭政治博客圈數(shù)據(jù)集上進行對比實驗。其中HEP-TH來源于arXiv，波蘭政治博客圈（Salon24）來源于www.salon24.pl網(wǎng)站。本文的實驗環(huán)境為Matlab R2018b(V9.5)。

3.1 參數(shù)確定

異同性分類模型共有兩個參數(shù)：、。對兩參數(shù)分別賦值，分析實驗結果以選擇最優(yōu)參數(shù)值。實驗中部分較優(yōu)結果如圖2和圖3所示。參數(shù)值的確定主要考慮兩方面，一是各類型演化事件數(shù)，二是演化事件總數(shù)。我們期望得到最多的演化結果(圖3)，但由圖2可知，當>0.3以后，Growing、Shrinking、Merging和Splitting數(shù)量以較快的速度減少，尤其是Growing、Merging和Splitting三類值急劇減少，最低值降為0，因此將值設置為0.3。同樣，綜合考慮演化事件總數(shù)及各類演化事件，將值設為0.2。以同樣方式對波蘭政治博客圈數(shù)據(jù)集進行分析，得出=0.3，=0.3時可得到最優(yōu)結果集。

圖2 不同參數(shù)下各類演化事件數(shù)

Table 2 Number of evolution events under different parameters

圖3 不同參數(shù)下總演化事件數(shù)

圖4 HEP-TH數(shù)據(jù)集演化模型對比結果

3.2 HEP-TH數(shù)據(jù)集實驗分析

為了進行對比試驗，選用HEP-TH和波蘭政治博客圈數(shù)據(jù)集。HEP-TH是高能物理理論引文網(wǎng)絡，每個節(jié)點代表一篇論文，邊代表引用關系，包含1993年1月至2003年4月共124個月的數(shù)據(jù)，共27770個節(jié)點，352807條邊。選取了1994年1月至1994年11月的數(shù)據(jù)，共3268個節(jié)點，7100條邊，將前后相鄰兩個月的數(shù)據(jù)劃分到一個時間窗口，2月至10月的數(shù)據(jù)會同時被前后兩個相鄰時間窗口所采集，因此共劃分為10個時間窗口。其中GED與SGCI的參數(shù)均選用論文中給出的最優(yōu)參數(shù)。實驗結果如圖4所示。

圖5 HEP-TH數(shù)據(jù)集社區(qū)節(jié)點數(shù)分析圖

圖6 波蘭政治博客圈數(shù)據(jù)集演化模型對比結果

結果顯示，對比GED與SGCI模型，提出的異同性演化分類模型可以較多地檢測到各類演化事件，例如Forming和Dissolving。分析數(shù)據(jù)集可知，GED和SGCI模型的演化判別條件對小社區(qū)不敏感，例如Forming事件要求包含度小于10%，而如圖5所示，HEP-TH數(shù)據(jù)集節(jié)點數(shù)小于10的社區(qū)個數(shù)占比為83.2%，要滿足“包含度小于10%”的條件很困難，因此不容易檢測到Forming事件。SGCI則是因為沒有Forming這一演化類型。除此以外，在其他事件檢測效果上與兩類模型差別不大。以上可知，提出的演化分類模型在綜合發(fā)現(xiàn)各類事件上有較強的優(yōu)勢，尤其對小社區(qū)同樣有較好的檢測結果。

3.3 波蘭政治博客圈數(shù)據(jù)集實驗分析

波蘭政治博客圈是SGCI論文所使用的數(shù)據(jù)集，源于www.salon24.pl網(wǎng)站的博客數(shù)據(jù)，主題主要是政治性的，也包括少量其他主題。數(shù)據(jù)集包括26722名用戶，285532條帖子和4173457條評論，時間跨度為2008年1月1日至2012年3月31日，每個月為一個時間窗，每個時間窗重疊15 d，共有104個時間窗。實驗結果如圖6所示。由圖表可知，提出的模型對Forming和Dissolving事件的檢測效果依然較好，在其他事件的檢測效果上與另外兩模型差別不大。其中SGCI檢測到Merging及Spliting的事件數(shù)相對較高是因為SGCI部分事件類型與GED不相同，GED的Merging和Addition事件都被劃分到了SGCI的Merging事件中，因此事件數(shù)相對較多；同樣其Spliting事件包括Spliting和Deletion兩類事件，數(shù)量也較多。因此獨立看待每個事件類型，本文模型整體要優(yōu)于GED及SGCI模型。

4 結語

本文提出了一種基于節(jié)點重要性評價指標p的差值吸收核心節(jié)點檢測算法，該算法以節(jié)點p值為基礎，對有邊連接的節(jié)點進行一一比對，得到核心節(jié)點組成核心節(jié)點集。該方法不需要設定參數(shù)，時間復雜度較低，且尋找核心節(jié)點的準確率較高。以此為基礎優(yōu)化差異性公式，從相似性和差異性兩方面對社區(qū)演化類型進行判定，提出了基于異同性的社區(qū)演化分類模型，并在HEP-TH和波蘭政治博客圈數(shù)據(jù)集上進行了有效驗證，結果表明本模型對Forming和Dissolving事件的檢測結果要優(yōu)于GED和SGCI分類模型。未來將對該演化分類模型進行優(yōu)化，提高Merging及Spliting等事件的檢測效果。

[1] Saganowski S. Predicting community evolution in social networks[C]//IEEE/ACM International Conference on Advances in Social Networks Analysis & Mining. Paris, France: IEEE, 2015

[2] 何婧.動態(tài)社交網(wǎng)絡社區(qū)發(fā)現(xiàn)及演化分析[D].徐州:中國礦業(yè)大學,2019

[3] ?lhan N, ??üdücü G?. Feature identification for predicting community evolution in dynamic social networks [J]. Engineering Applications of Artificial Intelligence, 2016,55:202-218

[4] Bhat SY, Abulaish M. HOCTracker: Tracking the evolution of hierarchical and overlapping communities in dynamic social networks [J]. IEEE Transactions on Knowledge & Data Engineering , 2015,27(4):1013-1019

[5] Yin G, Chi K, Dong Y,. An approach of community evolution based on gravitational relationship refact oring in dynamic networks [J]. Physics Letters A, 2017,381(16):1349-1355

[6] Dhouioui Z, Toujani R, Akaichi J. Tracking dynamic community evolution and events mobility in social networks [J]. Encyclopedia of Social Network Analysis and Mining, 2017,978:73-80

[7] Bródka P, Saganowski S, Kazienko P. GED: The method for group evolution discovery in social networks [J]. Social Network Analysis and Mining, 2012,3(1):1-14

[8] Gliwa B, Saganowski S, Zygmunt A,. Identification of group changes in blogosphere[C]// Proceedings of 2012 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM). Piscataway, New Jersey, USA: IEEE, 2012:1201-1206

[9] 任卓明,邵鳳,劉建國,等.基于度與集聚系數(shù)的網(wǎng)絡節(jié)點重要性度量方法研究[J].物理學報,2013,62(12):128901-1-5

[10] Zygmunt A, KoLak J, Nawarecki E,. Determining life cycles of evolving groups [J]. Procedia Computer Science, 2014,35:1102-1111

[11] Bommakanti SASR, Panda S. Events detection in temporally evolving social networks [C]//2018 IEEE International Conference on Big Knowledge. Singapore: IEEE, 2018:235-242

The Community Evolution Classification Method on Similarity and Difference

LIU Ye-qiang1, WANG Lu1, YANG Sheng-bin2*, LIU Ya-qiong2

1.271018,2.271018,

The analysis of community evolution in dynamic network is one of the current research hotspots, which plays an important role in public opinion control, network marketing, personalized recommendation service and so on. This paper proposes a nonparametric core node detection algorithm based on the evaluation index of node importance, which is used to find the core nodes in the community nodes to form the core node set, and to judge the difference of community based on the core node set. Based on this, a classification model of community evolution based on similarities and differences is proposed. This model determines the evolution relationship and divides the evolution type from the two aspects of similarities and differences. Comparing the proposed classification model with GED and SGCI in hep-th and Polish political blogosphere data sets, the experimental results show that the proposed classification model is better than GED and SGCI classification model on the whole. Especially in the detection of forming and dissolving events, it can be sensitive to small communities, and can detect a variety of evolution types of small communities.

Cluster coefficient; core node detection; classification model of community evolution

TP301.6

A

1000-2324(2021)03-0489-07

2020-01-07

2020-03-21

國家自然基金重大研究計劃(91746104);山東省重大科技創(chuàng)新工程項目(2019JZZY010706)

劉業(yè)強(2000-),男,本科,研究方向:智能信息處理. E-mail:364182723@qq.com

Author for correspondence. E-mail:ysb@sdau.edu.cn.