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

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

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

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

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

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

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

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

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

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

1 相關(guān)研究

1.1 節(jié)點(diǎn)重要性評(píng)價(jià)指標(biāo)

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

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

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

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

1.2 差異性公式

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

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

1.3 相似性公式

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

1.4 GED演化分類模型

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

每種演化類型判別如下：

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

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

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

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

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

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

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

2 算法描述

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

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

算法1差值吸收核心節(jié)點(diǎn)檢測算法 輸入：節(jié)點(diǎn)集V，邊集E 輸出：核心節(jié)點(diǎn)集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

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

圖1 10個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)圖

Fig.1 Network diagram of 10 nodes

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

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

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

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

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

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

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

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

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

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

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

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

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

本節(jié)首先提出差值吸收核心節(jié)點(diǎn)檢測算法，得到社區(qū)核心節(jié)點(diǎn)集和各節(jié)點(diǎn)的相對(duì)權(quán)重值(N)，以此為基礎(chǔ)改進(jìn)差異性公式，并將改進(jìn)的差異性公式應(yīng)用于演化類型的判定標(biāo)準(zhǔn)中，對(duì)演化類型進(jìn)行分類。

3 結(jié)果分析

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

3.1 參數(shù)確定

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

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

Table 2 Number of evolution events under different parameters

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

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

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

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

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

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

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

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

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

4 結(jié)語

本文提出了一種基于節(jié)點(diǎn)重要性評(píng)價(jià)指標(biāo)p的差值吸收核心節(jié)點(diǎn)檢測算法，該算法以節(jié)點(diǎn)p值為基礎(chǔ)，對(duì)有邊連接的節(jié)點(diǎn)進(jìn)行一一比對(duì)，得到核心節(jié)點(diǎn)組成核心節(jié)點(diǎn)集。該方法不需要設(shè)定參數(shù)，時(shí)間復(fù)雜度較低，且尋找核心節(jié)點(diǎn)的準(zhǔn)確率較高。以此為基礎(chǔ)優(yōu)化差異性公式，從相似性和差異性兩方面對(duì)社區(qū)演化類型進(jìn)行判定，提出了基于異同性的社區(qū)演化分類模型，并在HEP-TH和波蘭政治博客圈數(shù)據(jù)集上進(jìn)行了有效驗(yàn)證，結(jié)果表明本模型對(duì)Forming和Dissolving事件的檢測結(jié)果要優(yōu)于GED和SGCI分類模型。未來將對(duì)該演化分類模型進(jìn)行優(yōu)化，提高M(jìn)erging及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] 何婧.動(dòng)態(tài)社交網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)及演化分析[D].徐州:中國礦業(yè)大學(xué),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)絡(luò)節(jié)點(diǎn)重要性度量方法研究[J].物理學(xué)報(bào),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

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

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

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