何 偉,胡學(xué)鋼,李 磊,林耀進(jìn),李慧宗,潘劍寒

1(合肥工業(yè)大學(xué) 計(jì)算機(jī)與信息學(xué)院,合肥 230009)2(閩南大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院,福建 漳州 363000)3(安徽理工大學(xué) 經(jīng)濟(jì)與管理學(xué)院,安徽 淮南 232001)4(江蘇師范大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,江蘇 徐州 221116)

1 引 言

復(fù)雜網(wǎng)絡(luò)是對(duì)多主體交互或關(guān)聯(lián)的有效建模手段,現(xiàn)實(shí)世界中存在著大量的復(fù)雜網(wǎng)絡(luò)系統(tǒng),如 Internet 、WWW、社交網(wǎng)絡(luò)、科學(xué)家合作網(wǎng)絡(luò)、通信網(wǎng)絡(luò)、蛋白質(zhì)相互作用網(wǎng)絡(luò)、基因調(diào)控網(wǎng)絡(luò)等.信息技術(shù)的發(fā)展和海量數(shù)據(jù)的獲取,催生了對(duì)大規(guī)模復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)分析的需求,對(duì)復(fù)雜網(wǎng)絡(luò)的相關(guān)研究提出了挑戰(zhàn).

復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)描述了一種非均質(zhì)連接特性,即網(wǎng)絡(luò)由不同的節(jié)點(diǎn)簇所構(gòu)成,簇內(nèi)節(jié)點(diǎn)連接相對(duì)緊密,而簇間的連接相對(duì)稀疏[1].作為介于網(wǎng)絡(luò)微觀(guān)結(jié)構(gòu)和宏觀(guān)結(jié)構(gòu)之間的中尺度結(jié)構(gòu),社團(tuán)結(jié)構(gòu)是網(wǎng)絡(luò)中個(gè)體行為與整體功能之間的橋梁,對(duì)網(wǎng)絡(luò)的結(jié)構(gòu)和功能分析具有重要意義,針對(duì)社團(tuán)結(jié)構(gòu)物理意義和數(shù)學(xué)特性的研究也成為了近年來(lái)的熱點(diǎn)[2].

傳統(tǒng)的社團(tuán)結(jié)構(gòu)分析大多針對(duì)具有固定拓?fù)浣Y(jié)構(gòu)的靜態(tài)網(wǎng)絡(luò),實(shí)際網(wǎng)絡(luò)往往會(huì)隨著時(shí)間推移發(fā)生改變.例如,在科學(xué)家合作網(wǎng)絡(luò)中,新的研究者不斷加入,已有研究者也會(huì)退出;研究者之間的合作可能變得緊密,也可能變得稀疏;不同領(lǐng)域的研究者會(huì)開(kāi)展新的合作,原有合作也可能停止.這種變化導(dǎo)致網(wǎng)絡(luò)中社團(tuán)結(jié)構(gòu)的持續(xù)演化,傳統(tǒng)的靜態(tài)方法無(wú)法用于動(dòng)態(tài)性分析.

社團(tuán)演化預(yù)測(cè)通過(guò)分析歷史社團(tuán)數(shù)據(jù)判斷社團(tuán)的未來(lái)趨勢(shì),對(duì)理解動(dòng)態(tài)網(wǎng)絡(luò)結(jié)構(gòu)和功能具有重要意義.社團(tuán)演化預(yù)測(cè)通常分為社團(tuán)檢測(cè)、演化事件檢測(cè)、特征數(shù)據(jù)集構(gòu)造、分類(lèi)器訓(xùn)練幾個(gè)基本步驟.隨著社團(tuán)檢測(cè)、演化事件檢測(cè)兩類(lèi)前置研究的發(fā)展,社團(tuán)演化預(yù)測(cè)在近幾年受到了越來(lái)越多的關(guān)注.在社團(tuán)演化預(yù)測(cè)框架中,特征集構(gòu)造是難點(diǎn)和核心問(wèn)題之一.特征集的構(gòu)建以表示時(shí)序網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的一組矩陣數(shù)據(jù)、不同網(wǎng)絡(luò)快照中的社團(tuán)隸屬為輸入,目標(biāo)是提取出能夠完整準(zhǔn)確刻畫(huà)社團(tuán)結(jié)構(gòu)、時(shí)序變化的特征集合.已有研究存在兩個(gè)問(wèn)題:一方面,沒(méi)有完整考慮三種尺度(微觀(guān)、介觀(guān)、宏觀(guān))上的結(jié)構(gòu)信息;另一方面,構(gòu)造分類(lèi)器時(shí),采用固定長(zhǎng)度的演化鏈數(shù)據(jù)作為輸入,丟失了不同長(zhǎng)度演化鏈中蘊(yùn)含的時(shí)序信息.針對(duì)上述問(wèn)題,本文提出了基于多元結(jié)構(gòu)特征的社團(tuán)演化預(yù)測(cè)方法,從演化數(shù)據(jù)中中提取社團(tuán)的多尺度結(jié)構(gòu)特征、時(shí)序特征、行為特征,并針對(duì)多重長(zhǎng)度演化鏈構(gòu)造集成分類(lèi)器進(jìn)行預(yù)測(cè).

2 相關(guān)工作

2.1 動(dòng)態(tài)網(wǎng)絡(luò)及社團(tuán)演化事件檢測(cè)

Leskovec 等通過(guò)追蹤網(wǎng)絡(luò)拓?fù)涮卣鞯亩攘繉?duì)網(wǎng)絡(luò)演化進(jìn)行了分析,實(shí)驗(yàn)結(jié)果表明,隨著時(shí)間的推移和網(wǎng)絡(luò)規(guī)模的擴(kuò)大會(huì)發(fā)生一系列變化,如網(wǎng)絡(luò)變得更加稠密、度分布指數(shù)增大、有效直徑減小[3].2009年,Asur 針對(duì)動(dòng)態(tài)網(wǎng)絡(luò)中的節(jié)點(diǎn)定義了多種關(guān)鍵事件,提出了增量式的節(jié)點(diǎn)事件檢測(cè)方法,并分析探討了節(jié)點(diǎn)事件對(duì)社團(tuán)事件之間的關(guān)聯(lián)[4].

通過(guò)對(duì)科學(xué)家合作網(wǎng)絡(luò)和通話(huà)網(wǎng)絡(luò)進(jìn)行動(dòng)態(tài)分析,Palla 等發(fā)現(xiàn)社團(tuán)的生命周期與社團(tuán)內(nèi)的動(dòng)態(tài)行為以及社團(tuán)規(guī)模密切相關(guān),節(jié)點(diǎn)更替頻繁的大社團(tuán)和節(jié)點(diǎn)穩(wěn)定的小社團(tuán)能夠存在更久[5,6].同時(shí)他們首次定義了六種社團(tuán)演化事件,即社團(tuán)的擴(kuò)張、縮小、合并、分裂、形成和消亡.Takaffoli 提出了一種社團(tuán)演化追溯及事件檢測(cè)方法MODEC[7],該方法通過(guò)比較時(shí)序網(wǎng)絡(luò)中社團(tuán)的相似度來(lái)追蹤演化中的社團(tuán),定義了相關(guān)規(guī)則用于判定Palla提出的六種演化事件.該研究還分析了時(shí)序網(wǎng)絡(luò)中節(jié)點(diǎn)行為與社團(tuán)演化事件之間的關(guān)聯(lián),提出少數(shù)影響力高的節(jié)點(diǎn)行為與演化事件之間相關(guān)性較高.在Palla提出的演化事件基礎(chǔ)上,Bródka等提出了一種演化事件檢測(cè)方法GED[8].該方法首先采用最大團(tuán)過(guò)濾算法CPM找出靜態(tài)社團(tuán)結(jié)構(gòu),再通過(guò)比較連續(xù)時(shí)間片中社團(tuán)的大小、相互包容度(inclusion)來(lái)發(fā)現(xiàn)連續(xù)社團(tuán).

Gliwa等定義了一組社團(tuán)演化事件:穩(wěn)定、規(guī)模變化、分離、附加、分裂、合并、分裂后合并、衰退[9].同時(shí)提出了一種社團(tuán)演化追蹤方法 SGCI,其基本思想是在固定長(zhǎng)度的時(shí)間窗口中尋找持續(xù)性的社團(tuán),判斷標(biāo)準(zhǔn)為社團(tuán)在特定長(zhǎng)度時(shí)間窗口內(nèi)的存活時(shí)間超過(guò)閾值.

2.2 演化社團(tuán)預(yù)測(cè)

Bródka在GED演化事件檢測(cè)的基礎(chǔ)上提出了社團(tuán)演化預(yù)測(cè)的基本流程,并在四個(gè)實(shí)際網(wǎng)絡(luò)數(shù)據(jù)上驗(yàn)證了該方法的可行性[10].該研究采用前序社團(tuán)的演化事件和社團(tuán)尺寸作為分類(lèi)特征,預(yù)測(cè)精度較低,且受參數(shù)影響大.2013年,Bródka和Gliwa等合作,在GED和SGCI兩種演化事件檢測(cè)方法的基礎(chǔ)上對(duì)博客圈進(jìn)行社團(tuán)演化預(yù)測(cè)[11].特征集構(gòu)造抽取了多種社團(tuán)的介觀(guān)特征,包括社團(tuán)的中心性、外鏈邊密度、內(nèi)聚性和尺寸,同時(shí)對(duì)比不同分類(lèi)方法的預(yù)測(cè)準(zhǔn)確率.實(shí)驗(yàn)表明該方法較Bródka的預(yù)測(cè)方法在準(zhǔn)確性上有所提升,針對(duì)不同事件的分類(lèi)器效果存在差異.在不同網(wǎng)絡(luò)中的事件頻次統(tǒng)計(jì)表明,兩種演化事件檢測(cè)方法都存在類(lèi)別傾斜的問(wèn)題,SGCI方法檢測(cè)出大量的附加事件,GEB方法則檢測(cè)出大量的分裂事件.后續(xù)工作中,Saganowski等結(jié)合社團(tuán)結(jié)構(gòu)信息和推文相關(guān)信息構(gòu)造特征集,改進(jìn)了分類(lèi)流程,加入了特征選擇和交叉驗(yàn)證步驟,將預(yù)測(cè)方法擴(kuò)展到了帶有向邊的社交網(wǎng)絡(luò)中[12].在構(gòu)造特征集時(shí),除原有介觀(guān)特征外,額外考慮了社團(tuán)內(nèi)節(jié)點(diǎn)互惠性和多種微觀(guān)特征聚合,微觀(guān)特征包括節(jié)點(diǎn)度數(shù)、入度、出度、介數(shù)中心性、接近中心性、奇異值中心性,聚合方式包括求和、平均、最小和最大.該研究還對(duì)采用不同長(zhǎng)度演化鏈數(shù)據(jù)的分類(lèi)準(zhǔn)確性進(jìn)行了對(duì)比.對(duì)基于SGCI方法提取的連續(xù)社團(tuán),演化預(yù)測(cè)準(zhǔn)確率隨著演化鏈增長(zhǎng)而逐漸提高;對(duì)基于GED方法提取的連續(xù)社團(tuán),準(zhǔn)確率不一定隨演化鏈增長(zhǎng)而提高.

Diakidis等用同樣的方法對(duì)2014世界杯相關(guān)的推文信息網(wǎng)絡(luò)進(jìn)行了社團(tuán)演化預(yù)測(cè),文章實(shí)驗(yàn)中實(shí)驗(yàn)對(duì)比了多種分類(lèi)器的分類(lèi)結(jié)果并分析了不同持續(xù)時(shí)間社團(tuán)中各種特征的信息增益[13].

Takaffoli在MODEC演化模型的基礎(chǔ)上提出了一種綜合利用關(guān)鍵節(jié)點(diǎn)信息、社團(tuán)結(jié)構(gòu)信息、歷史事件信息及社交網(wǎng)絡(luò)主題信息的社團(tuán)演化預(yù)測(cè)方法[14].實(shí)驗(yàn)采用了不同分類(lèi)算法對(duì)郵件通信網(wǎng)絡(luò)和科學(xué)家合作網(wǎng)絡(luò)進(jìn)行了預(yù)測(cè),并考察了不同特征與各類(lèi)演化事件的相關(guān)性.

2016年,Shahriari等采用GED方法檢測(cè)演化事件,針對(duì)社團(tuán)中關(guān)鍵節(jié)點(diǎn)信息、社團(tuán)結(jié)構(gòu)信息、時(shí)序和歷史事件信息構(gòu)造特征集并進(jìn)行分類(lèi)[15].通過(guò)對(duì)多類(lèi)網(wǎng)絡(luò)的預(yù)測(cè)和分析,找出了不同網(wǎng)絡(luò)中持久社團(tuán)的特點(diǎn),以及不同特征與演化事件的相關(guān)性.

3 基于多元特征的社團(tuán)演化預(yù)測(cè)方法

社團(tuán)演化預(yù)測(cè)過(guò)程分為以下四步:提取網(wǎng)絡(luò)快照中的社團(tuán)結(jié)構(gòu);檢測(cè)各時(shí)間窗口的演化事件,獲取類(lèi)別標(biāo)簽;根據(jù)社團(tuán)演化數(shù)據(jù)構(gòu)造特征數(shù)據(jù)集;用得到的數(shù)據(jù)集訓(xùn)練分類(lèi)器,進(jìn)行預(yù)測(cè).

3.1 社團(tuán)檢測(cè)和演化事件檢測(cè)

本文采用GED方法檢測(cè)時(shí)序快照中的連續(xù)社團(tuán)和演化事件[9].GED方法定義了圖G1在圖G2中的包容度I(G1,G2)作為判斷一個(gè)圖對(duì)另一個(gè)圖的包含程度:

其中NIG1(x)為節(jié)點(diǎn)x在圖G1中的影響力度量.乘積的左邊項(xiàng)度量了圖G2節(jié)點(diǎn)在圖G1中所占比例,右邊項(xiàng)度量了G2中共同節(jié)點(diǎn)與G1中節(jié)點(diǎn)在社團(tuán)中影響力聚合是否相近,兩者結(jié)合同時(shí)度量了數(shù)量和質(zhì)量上的包含程度.以該度量為基礎(chǔ),GED定義并檢測(cè)七種演化事件,包括維持、擴(kuò)張、縮小、合并、分裂、形成和消亡.

3.2 特征集構(gòu)造

為完整準(zhǔn)確地刻畫(huà)社團(tuán)演化特性,本文抽取結(jié)構(gòu)、時(shí)序、行為三類(lèi)特征,其中結(jié)構(gòu)特征反映三種不同尺度下的社團(tuán)拓?fù)涮匦?時(shí)序特征反映從前序社團(tuán)到后續(xù)社團(tuán)的改變,行為特征為前一時(shí)間窗口發(fā)生的演化事件.

3.2.1 結(jié)構(gòu)特征

1)微觀(guān)結(jié)構(gòu)特征

微觀(guān)層面的節(jié)點(diǎn)行為是介觀(guān)層面社團(tuán)和宏觀(guān)層面網(wǎng)絡(luò)演化的根源,微觀(guān)結(jié)構(gòu)特征考察社團(tuán)中節(jié)點(diǎn)的相關(guān)特性.網(wǎng)絡(luò)中的節(jié)點(diǎn)占據(jù)不同的結(jié)構(gòu)位、具有不同的行為,角色是對(duì)其結(jié)構(gòu)位或行為的抽象,一些關(guān)鍵角色對(duì)社團(tuán)演化有較大的影響[16].本文針對(duì)網(wǎng)絡(luò)中心、社團(tuán)核心、中介三種關(guān)鍵角色抽取特征.

網(wǎng)絡(luò)中心是在整體網(wǎng)絡(luò)中具有強(qiáng)影響力的節(jié)點(diǎn),本文用概率分布接近正態(tài)分布的接近中心度(Closeness Centrality)作為節(jié)點(diǎn)的影響力度量,計(jì)算所有節(jié)點(diǎn)的接近中心度,求出分布均值μ和方差σ,將中心度大于閾值μ+2σ的節(jié)點(diǎn)(正態(tài)分布的95%置信區(qū)間為[μ-2σ,μ+2σ])視作網(wǎng)絡(luò)中心.社團(tuán)核心是社團(tuán)內(nèi)部的高影響力節(jié)點(diǎn),本文采用與網(wǎng)絡(luò)中心同樣的方法在社團(tuán)子圖(僅包含內(nèi)部連邊)中進(jìn)行提取.中介是連接不同社團(tuán)的關(guān)鍵節(jié)點(diǎn),本文采用CPM算法得到重疊社團(tuán),將重疊節(jié)點(diǎn)視作中介節(jié)點(diǎn).表1列出了針對(duì)三類(lèi)角色所構(gòu)造的微觀(guān)結(jié)構(gòu)特征.

表1 社團(tuán)微觀(guān)結(jié)構(gòu)特征Table 1 Microscopic structural feature of community

2)介觀(guān)結(jié)構(gòu)特征

介觀(guān)結(jié)構(gòu)特征考察社團(tuán)自身的結(jié)構(gòu)特征,表2列出了本文構(gòu)造的介觀(guān)結(jié)構(gòu)特征.

其中內(nèi)聚度為社團(tuán)內(nèi)邊密度與社團(tuán)外邊密度的比值,對(duì)于圖G(V,E)中的社團(tuán)C(VC,EC),其與社團(tuán)外節(jié)點(diǎn)的連接數(shù)為OEC,內(nèi)聚度計(jì)算公式為:

圖G(V,E)中節(jié)點(diǎn)i的集聚系數(shù)ClusterCoefi定義為i所有鄰居所構(gòu)成子圖的邊密度,全局集聚系數(shù)定義為圖中所有節(jié)點(diǎn)集聚系數(shù)的均值:

度數(shù)中心度用于度量網(wǎng)絡(luò)中節(jié)點(diǎn)度數(shù)的差異程度,圖G(V,E)的度數(shù)中心度定義如下:

其中Di為節(jié)點(diǎn)i的度數(shù),Dmax為所有所有節(jié)點(diǎn)度數(shù)的最大值.

表2 社團(tuán)介觀(guān)結(jié)構(gòu)特征Table 2 Mesoscopic structural feature of community

3)宏觀(guān)結(jié)構(gòu)特征

宏觀(guān)結(jié)構(gòu)特征將社團(tuán)看做整體,反映其在全局和局部環(huán)境中的影響力和相對(duì)特性,表3列出了本文抽取的宏觀(guān)結(jié)構(gòu)特征.

表3 社團(tuán)宏觀(guān)結(jié)構(gòu)特征Table 3 Macroscopic structural feature of community

整體網(wǎng)絡(luò)是社團(tuán)所處的全局環(huán)境,為考察社團(tuán)其在整個(gè)網(wǎng)絡(luò)中的相關(guān)特性,首先構(gòu)建社團(tuán)網(wǎng)絡(luò)(network of communities),即把社團(tuán)看做節(jié)點(diǎn),根據(jù)社團(tuán)重疊與否確定節(jié)點(diǎn)間是否連邊,重疊節(jié)點(diǎn)個(gè)數(shù)作為邊的權(quán)重.本文采用社團(tuán)節(jié)點(diǎn)在社團(tuán)網(wǎng)絡(luò)中的PageRank值度量社團(tuán)在全局環(huán)境中的影響力,用微觀(guān)、介觀(guān)特征在所有社團(tuán)中的歸一化值度量社團(tuán)的全局相對(duì)特性.

與社團(tuán)相鄰的所有社團(tuán)及其連邊構(gòu)成其局部環(huán)境,首先需要構(gòu)造由社團(tuán)與其鄰接社團(tuán)構(gòu)成的中心網(wǎng)絡(luò)(ego network).本文采用社團(tuán)在中心網(wǎng)絡(luò)內(nèi)的結(jié)構(gòu)洞值[17]度量社團(tuán)在局部環(huán)境中的影響力,采用微觀(guān)、介觀(guān)特征在中心網(wǎng)絡(luò)中的歸一化值度量社團(tuán)的局部相對(duì)特性.

3.2.2 時(shí)序特征

時(shí)序特征包括前一時(shí)間窗口內(nèi)發(fā)生的變動(dòng)、社團(tuán)已存活時(shí)間、后序社團(tuán)與前序社團(tuán)的相似和差異(表4).

表4 社團(tuán)時(shí)序特征Table 4 Sequential feature of community

3.2.3 行為特征

行為特征為當(dāng)前時(shí)間窗口的形成、維持、合并、分裂、尺寸變化(擴(kuò)張和縮小)五類(lèi)事件,表5列出了本文抽取的行為特征.

表5 社團(tuán)行為特征Table 5 Behaviour feature of community

3.2.4 演化鏈特征樣本

表6 預(yù)測(cè)事件及類(lèi)別標(biāo)簽Table 6 Prediction event and classification label

3.3 分類(lèi)器訓(xùn)練和預(yù)測(cè)

由于有多個(gè)類(lèi)別標(biāo)簽,本文采用One vs Rest策略對(duì)五類(lèi)事件分別構(gòu)造分類(lèi)器.已有方法針對(duì)所有事件都采取固定長(zhǎng)度演化鏈訓(xùn)練分類(lèi)器,但不同長(zhǎng)度演化鏈蘊(yùn)含的時(shí)序信息有差異,最優(yōu)長(zhǎng)度與網(wǎng)絡(luò)類(lèi)型、具體演化事件相關(guān).使用固定長(zhǎng)度演化鏈無(wú)法充分利用不同長(zhǎng)度演化鏈中蘊(yùn)含的信息,也不能適應(yīng)各類(lèi)網(wǎng)絡(luò)和演化事件[12].為解決該問(wèn)題,本文提出一種多長(zhǎng)度演化鏈集成(Multi-length Evolution Chains Ensemble)分類(lèi)方法,以不同長(zhǎng)度演化鏈作為輸入,分別構(gòu)造分類(lèi)器.基分類(lèi)器的選擇無(wú)特殊限定,此處采用Random Forest作為基分類(lèi)器(圖1).

圖1 利用不同長(zhǎng)度演化鏈的集成分類(lèi)器MECEFig.1 Ensemble classifier MECE using multi-length evolution chains

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

4.1 數(shù)據(jù)及預(yù)處理

本文使用郵件通信網(wǎng)絡(luò)Enron*http://www.cs.cmu.edu/～enron/和科學(xué)家合作網(wǎng)絡(luò)DBLP*http://projects.csail.mit.edu/dnd/DBLP/兩個(gè)數(shù)據(jù)集,表7列出了數(shù)據(jù)集的基本統(tǒng)計(jì)信息.

Enron 數(shù)據(jù)集記錄了安然公司32個(gè)月內(nèi)的電子郵件通信.原始網(wǎng)絡(luò)數(shù)據(jù)為有環(huán)有向多邊無(wú)權(quán)圖,每個(gè)節(jié)點(diǎn)代表一位安然員工,每條邊代表一封郵件,方向?yàn)猷]件發(fā)送方到接收方.本文對(duì)Enron數(shù)據(jù)集按月劃分,節(jié)點(diǎn)集合為整個(gè)網(wǎng)絡(luò)中最大弱連通分支中的節(jié)點(diǎn),忽略邊的方向,合并節(jié)點(diǎn)對(duì)之間的邊并刪除所有的環(huán),每條邊的權(quán)值為當(dāng)前時(shí)間窗口內(nèi)兩點(diǎn)間的郵件數(shù).

DBLP記錄了32年間的計(jì)算機(jī)領(lǐng)域論文合作情況.原始網(wǎng)絡(luò)數(shù)據(jù)為無(wú)環(huán)無(wú)向多邊無(wú)權(quán)圖,每個(gè)節(jié)點(diǎn)代表一位科學(xué)家,每條邊代表一次論文合作.本文對(duì)DBLP數(shù)據(jù)集按年劃分,節(jié)點(diǎn)集合為整個(gè)網(wǎng)絡(luò)中最大連通分支中的節(jié)點(diǎn),合并節(jié)點(diǎn)對(duì)之間的邊,每條邊的權(quán)值為當(dāng)前時(shí)間窗口內(nèi)兩位科學(xué)家的合作次數(shù).

其中γ∈(0,1)為衰減系數(shù),離當(dāng)前時(shí)間點(diǎn)越久遠(yuǎn)權(quán)值衰減越嚴(yán)重,此處令γ=0.5.

4.2 參數(shù)設(shè)置

4.3 實(shí)驗(yàn)結(jié)果

分別通過(guò)已有研究中的方法[10,14]與本文構(gòu)造特征集合(分別表示為F_10、F_14、F),用RandomForest方法[18]和本文MECE方法構(gòu)造分類(lèi)器(分別為RF和MECE),其中RF分類(lèi)器以長(zhǎng)度為4的演化鏈作為輸入數(shù)據(jù),MECE方法中演化鏈最大長(zhǎng)度為10,采用十折交叉驗(yàn)證求出平均F1值(表8,表9).

表8 Enron數(shù)據(jù)集上不同特征和分類(lèi)器組合得到的平均F1值Table 8 Average F1 scores of Enron dataset classification results combining different features and classifier

表9 DBLP數(shù)據(jù)集上不同特征和分類(lèi)器組合得到的平均F1值Table 9 Average F1 scores of Enron dataset classification results combining different features and classifier

由表8、表9中前三列數(shù)據(jù)可以看出,對(duì)于Enron和DBLP的五種事件,在同樣采用RF分類(lèi)器的情況下,本文所構(gòu)造的特征能更有效地刻畫(huà)社團(tuán)特性,預(yù)測(cè)準(zhǔn)確率更高.研究[10]中通過(guò)歸一化和聚合節(jié)點(diǎn)特征獲取了多種社團(tuán)結(jié)構(gòu)特征,但缺乏關(guān)鍵節(jié)點(diǎn)特征、時(shí)序特征(社團(tuán)結(jié)構(gòu)特征與前序社團(tuán)結(jié)構(gòu)特征的差異).研究[14]所構(gòu)造的介觀(guān)特征中則遺漏了社團(tuán)尺寸這一關(guān)鍵特征,也沒(méi)有構(gòu)造社團(tuán)的宏觀(guān)特征.由表8、表9中后兩列數(shù)據(jù)可看出,針對(duì)多重長(zhǎng)度演化鏈的集成分類(lèi)方法MECE具有更高的預(yù)測(cè)準(zhǔn)確率.

5 結(jié)束語(yǔ)

社團(tuán)演化預(yù)測(cè)研究對(duì)理解網(wǎng)絡(luò)結(jié)構(gòu)和功能具有重要意義,隨著動(dòng)態(tài)網(wǎng)絡(luò)數(shù)據(jù)的不斷累積,該研究將具有越來(lái)越廣泛的應(yīng)用前景.本文提出了一種基于多元特征構(gòu)造的社團(tuán)演化預(yù)測(cè)方法,通過(guò)在網(wǎng)絡(luò)快照中構(gòu)造社團(tuán)多尺度結(jié)構(gòu)特征、時(shí)序特征、行為特征,有效刻畫(huà)了社團(tuán)的結(jié)構(gòu)和動(dòng)態(tài)特性,并將不同長(zhǎng)度的演化鏈數(shù)據(jù)用于集成分類(lèi)器訓(xùn)練.實(shí)驗(yàn)表明了本文特征構(gòu)造方法的有效性和分類(lèi)方法的準(zhǔn)確性.

：

[1] Girvan,Michelle,and Mark EJ Newman.Community structure in social and biological networks[C].Proceedings of the National Academy of Sciences 99,2002,12:7821-7826.

[2] Fortunato,Santo.Community detection in graphs[R].Physics Reports 486,2010,3:75-174.

[3] Leskovec Jure,Jon Kleinberg,Christos Faloutsos.Graphs over time:densification laws,shrinking diameters and possible explanations[C].Proceedings of the Eleventh ACM SIGKDD International Conference on Knowledge Discovery in Data Nining,ACM,2005:177-187.

[4] Asur Sitaram,Srinivasan Parthasarathy,Duygu Ucar.An event-based framework for characterizing the evolutionary behavior of interaction graphs[C].ACM Transactions on Knowledge Discovery from Data (TKDD)3,2009，4:16.

[5] Palla Gergely,Albert-László Barabási,et al.Community dynamics in social networks[J].Fluctuation and Noise Letters 7,2007,(3):273-287.

[6] Palla Gergely,Albert-László Barabási, Tamás Vicsek.Quantifying social group evolution[J].Nature,2007,446(7136):664-667.

[7] Takaffoli,Mansoureh,Justin Fagnan,Farzad Sangi,et al.Tracking changes in dynamic information networks[C].Computational Aspects of Social Networks (CASoN),2011 International Conference on,IEEE,2011:94-101.

[8] Bródka Piotr,Stanisaw Saganowski,Przemysaw Kazienko.GED:the method for group evolution discovery in social networks[J].Social Network Analysis and Mining,2013:1-14.

[9] Gliwa Bogdan,Anna Zygmunt,Aleksander Byrski.Graphical analysis of social group dynamics[C].Computational Aspects of Social Networks (CASoN),2012 Fourth International Conference on,IEEE,2012:41-46.

[10] Bródka Piotr,Przemysaw Kazienko,Bartosz Kooszczyk.Predicting group evolution in the social network[C].International Conference on Social Informatics,Springer Berlin Heidelberg,2012:54-67.

[11] Gliwa Bogdan,Piotr Bródka,Anna Zygmunt,et al.Different approaches to community evolution prediction in blogosphere[C].Proceedings of the 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining,ACM,2013:1291-1298.

[12] Saganowski Stanisaw,Bogdan Gliwa,Piotr Bródka,et al.Predicting community evolution in social networks[J].Entropy,2015,17(5):3053-3096.

[13] Diakidis Georgios,Despoina Karna,Dimitris Fasarakis-Hilliard,et al.Predicting the evolution of communities in social networks[C].Proceedings of the 5th International Conference on Web Intelligence,Mining and Semantics,ACM,2015.

[14] Takaffoli,Mansoureh,Reihaneh Rabbany,Osmar R.Za?ane.Community evolution prediction in dynamic social networks[C].Advances in Social Networks Analysis and Mining (ASONAM),2014 IEEE/ACM International Conference on,2014.

[15] Shahriari Mohsen,Stephen Gunashekar,Marven von Domarus,et al.Predictive analysis of temporal and overlapping community structures in social media[C].Proceedings of the 25th International Conference Companion on World Wide Web,International World Wide Web Conferences Steering Committee,2016.

[16] Fagnan Justin,Reihaneh Rabbany,Mansoureh Takaffoli,et al.Community dynamics:event and role analysis in social network analysis[C].International Conference on Advanced Data Mining and Applications,Springer International Publishing,2014.

[17] Burt,Ronald S.Structural hole[M].Harvard Business School Press,Cambridge,MA,1992.

[18] Breiman,Leo.Random forests[J].Machine Learning,2001,45 (1):5-32.