傳播結(jié)果的同源分析

摘要：傳播結(jié)果的同源分析旨在識別出哪些歷史傳播結(jié)果是由同一組傳播源頭產(chǎn)生的。使用伯努利混合模型對傳播結(jié)果的同源分析問題進行建模求解，同一組源頭產(chǎn)生的傳播結(jié)果對應(yīng)一個伯努利分量，而伯努利分量的參數(shù)反映源頭的影響在各點的傳播到達概率；基于該模型和觀測數(shù)據(jù)構(gòu)建對數(shù)似然函數(shù)，并使用EM算法求解其中的伯努利參數(shù)，確定同源分析的結(jié)果。大量實驗結(jié)果證明，對比于傳統(tǒng)聚類算法，提出算法同源聚類的準確度更高，能夠更高效準確地對傳播結(jié)果數(shù)據(jù)進行同源分析。

關(guān)鍵詞：傳播網(wǎng)絡(luò)；同源分析；伯努利混合模型；EM算法；聚類

中圖分類號：TP391文獻標志碼：A

文章編號：1001-3695（2022）10-008-2943-07

doi：10.19734/j.issn.1001-3695.2022.03.0141

Homology analysis of diffusion results

Yang Xuan1，Xu Beicheng2，Yao Chang3，Huang Hao2

（1.Women’s Hospital，School of Medicine，Zhejiang University，Hangzhou 310006，China；2.School of Computer Science，Wuhan University，Wuhan 430072，China；3.College of Computer Science amp; Technology，Zhejiang University，Hangzhou 310027，China）

Abstract：The homology analysis of diffusion results aimed to identify which historical diffusion results were produced by the same set of diffusion sources.This paper used Bernoulli mixture model to solve this problem.The diffusion results generated by the same group of sources corresponded to the same Bernoulli component，and the parameters of the corresponding Bernoulli component reflected the arrival probability of the sources’ influence at each point.Then it constructed the log-likelihood function based on the model and the observed data，and used the EM algorithm to calculate the Bernoulli parameters in the log-likelihood function to determine the results of homology analysis.A large number of experimental results verify that compared with the traditional clustering algorithm，the proposed algorithm in this paper can get higher accuracy of the homologous clustering.That is to say，the proposed algorithm can perform homology analysis on the propagation result data more efficiently and accurately.

Key words：diffusion network；homologous analysis；Bernoulli mixture model；EM algorithm；clustering

0引言

傳播網(wǎng)絡(luò)是一個代表節(jié)點之間相互影響關(guān)系的有向圖，它將最先產(chǎn)生信息或被感染的節(jié)點視為網(wǎng)絡(luò)中的傳播源頭，當信息或疾病/在源頭率先產(chǎn)生時，接受信息或被感染的節(jié)點將其沿著代表節(jié)點間影響關(guān)系的有向邊進行傳播，造成信息/疾病的逐步擴散/感染。傳播結(jié)果的同源分析旨在對傳播網(wǎng)絡(luò)中產(chǎn)生的大量傳播結(jié)果進行擬合，模擬各組源頭產(chǎn)生的傳播特征，將傳播結(jié)果按源頭劃分，以便更好地分析傳播源和被感染節(jié)點之間的關(guān)系。

傳播結(jié)果的同源分析基于傳播過程結(jié)束后節(jié)點的感染狀態(tài)數(shù)據(jù)，旨在找出哪些傳播結(jié)果源自于同一組傳播源頭。當傳播網(wǎng)絡(luò)結(jié)構(gòu)和傳播源頭已知時，傳播源對其他節(jié)點產(chǎn)生影響的概率可以直接計算得到，從而根據(jù)貝葉斯定理可以推測各個傳播結(jié)果是由哪組源頭影響產(chǎn)生的。然而在現(xiàn)實中，傳播網(wǎng)絡(luò)的確切結(jié)構(gòu)和傳播源頭都難以被準確地獲得，而且源頭也往往是要找尋的目標，最方便得到的只有傳播過程結(jié)束后節(jié)點的感染狀態(tài)數(shù)據(jù)（通常狀態(tài)“1”表示節(jié)點被感染，接受了某一傳播內(nèi)容；狀態(tài)“0”表示節(jié)點未被感染，未接受該傳播內(nèi)容）。本文基于上述狀態(tài)數(shù)據(jù)進行同源分析。

本文提出的傳播結(jié)果的同源分析問題不同于生物醫(yī)學(xué)領(lǐng)域的同源分析問題，醫(yī)學(xué)領(lǐng)域的“同源”指的是有相同的基因源，可通過分析基因源的異同在蛋白質(zhì)、DNA等序列的數(shù)據(jù)庫中尋找代表集，排除冗余［1］；還有將蛋白質(zhì)序列聚類成有生物學(xué)意義的同源（家族）組［2，3］等。這些與本文對傳播結(jié)果進行劃分實現(xiàn)同源分析的目標不一致，本文的同源指的是有同一組傳播源頭，希望將同一源頭產(chǎn)生的傳播結(jié)果聚集到一起。

與本文問題在形式上更接近的是聚類問題，但聚類算法應(yīng)用于傳播結(jié)果的同源分析時也存在局限性。常見的聚類算法包括：a）基于劃分的聚類算法，迭代地將對象劃分到各簇并更新簇的中心或者代表點；b）基于層次的聚類算法，自底而上或自頂而下更新不同層次下的分類情況；c）基于圖的聚類算法，其將聚類問題轉(zhuǎn)換為子圖劃分問題；d）基于密度的聚類算法，其將數(shù)據(jù)集中密度相連的對象聚為一類。上述聚類算法雖然有一定的有效性，卻并非為同源分析所提出，與本文問題背景結(jié)合不緊密，具體體現(xiàn)在：a）上述許多算法都依靠距離對數(shù)據(jù)進行相似性度量，而距離的計算方法（如歐氏距離、曼哈頓距離、余弦距離等） 繁多難以確定，本文數(shù)據(jù)集中的傳播結(jié)果只有被感染和未被感染兩種取值，并且同一組源頭產(chǎn)生的節(jié)點感染狀態(tài)結(jié)果就存在很大的不確定性，只考慮記錄向量間距離與問題背景結(jié)合性不強，數(shù)據(jù)特征利用也不充分；b）本文要使用模型對各組源頭產(chǎn)生的傳播進行模擬，得到傳播網(wǎng)絡(luò)中各節(jié)點狀態(tài)的概率分布，進而能夠?qū)Ω鱾鞑ソY(jié)果實現(xiàn)按概率劃分。但是上述方法只是單純地對結(jié)果進行了聚類，難以將聚類結(jié)果和數(shù)據(jù)產(chǎn)生機理進行結(jié)合，結(jié)果缺乏可解釋性。

為避免上述算法的局限性，本文通過伯努利混合模型對傳播結(jié)果數(shù)據(jù)進行概率擬合，從而將同源分析問題轉(zhuǎn)換為伯努利混合模型求解問題。每一組源頭所產(chǎn)生的傳播過程對應(yīng)于模型中的一個伯努利分量，該組中所有源頭的影響融合到該伯努利分量的伯努利參數(shù)中，反映了信息或者疾病在各節(jié)點的到達概率；然后構(gòu)建對數(shù)似然函數(shù)計算該模型對傳播結(jié)果數(shù)據(jù)的擬合程度，并使用EM算法迭代求解似然度函數(shù)最優(yōu)時的伯努利參數(shù)。每輪迭代先對所有傳播結(jié)果確定其所屬的同源類，再通過每個同源類中的數(shù)據(jù)更新對應(yīng)的伯努利分量參數(shù)，直到模型收斂，最后再確定傳播結(jié)果數(shù)據(jù)的劃分，實現(xiàn)了在未知源頭、未知網(wǎng)絡(luò)結(jié)構(gòu)情況下的傳播結(jié)果同源分析。此外，為減少EM算法迭代的次數(shù)，本文模型使用了Lance-Williams算法優(yōu)化的Ward-linkage層次聚類來初始化伯努利參數(shù)，實現(xiàn)了算法的快速收斂。在不同傳播網(wǎng)絡(luò)、不同傳播參數(shù)以及不同數(shù)據(jù)量上的實驗結(jié)果驗證了本文模型的有效性、較高的效率及可解釋性。

傳播結(jié)果的同源分析對于現(xiàn)實生活中社區(qū)輿情監(jiān)測［4］以及流感傳染病防治［5］等領(lǐng)域的工作具有重要意義，它能夠為傳播網(wǎng)絡(luò)中的影響最大化［6，7］以及不依賴時間信息的拓撲結(jié)構(gòu)推斷［8～12］等工作奠基，提供豐富的素材和樣本；它能夠為傳播網(wǎng)絡(luò)源頭分析進行數(shù)據(jù)去噪或數(shù)據(jù)壓縮，提供產(chǎn)生于同一組源頭的暴發(fā)結(jié)果樣本。因此，同源分析有利于在醫(yī)學(xué)和輿情監(jiān)測等領(lǐng)域更好地預(yù)測、促進或者阻止未來的傳播事件［13］。本文的主要貢獻包括以下三個方面：a）首次顯式地提出傳播結(jié)果的同源分析問題，并提出了一種基于混合伯努利模型的求解方法，通過分析傳播網(wǎng)絡(luò)的傳播記錄將產(chǎn)生自同一組源頭的記錄聚類到一起；b）提出了以Ward-linkage層次聚類為參數(shù)初始化方法的混合伯努利模型，在提升模型準確率的同時減少了迭代次數(shù)。用不同數(shù)據(jù)集上的大量實驗驗證了提出的傳播結(jié)果同源分析算法可以有效地對傳播結(jié)果進行聚類。

1相關(guān)工作

本文首次顯式地提出同源分析問題，目標是從傳播網(wǎng)絡(luò)產(chǎn)生的傳播結(jié)果集中將產(chǎn)生自同源的記錄聚類，排除噪聲，為后續(xù)溯源等工作奠定基礎(chǔ)。與本文研究問題相似的是一系列對數(shù)據(jù)進行劃分的聚類算法，這些聚類算法可以分為基于劃分的、基于層次的、基于圖的、基于密度的聚類算法和其他聚類算法。

1.1基于劃分的聚類算法

基于劃分的聚類算法將數(shù)據(jù)劃分為K個不同的簇，使得同一個簇中的對象盡可能地接近，而不同簇中的對象盡可能地遠離。通常采用迭代更新的策略不斷地重新劃分數(shù)據(jù)集并更新參數(shù)，直到模型收斂。最常用的劃分聚類算法有K-means算法［14］和K-medoids算法［15］以及它們的一些拓展算法［16～18］等。K-means算法使用簇的中心代表該簇，劃分時通過比較某對象到各簇中心的距離來判斷其歸屬，劃分結(jié)束后，計算各簇新的中心。模型不斷迭代直到某輪形成的簇與前一輪相同，達到收斂狀態(tài)。K-medoids算法使用代表對象來代表某簇，劃分時將每個對象分配到最近的代表對象所代表的簇，然后隨機選擇非代表對象與一個代表對象交換，計算交換代價，如果數(shù)據(jù)集中所有對象與其代表對象間距離和減小，則接受此次交換，否則拒絕。如此迭代直到所有代表對象都不能被替換，模型收斂。相對于K-means，K-medoids在存在噪聲和離群點時具有更高的魯棒性，但由于每輪迭代需要嘗試交換所有代表對象和非代表對象，K-medoids算法的時間復(fù)雜度更高，不適用于大數(shù)據(jù)集。

1.2基于層次的聚類算法

基于層次的聚類算法將數(shù)據(jù)劃分為不同層上的簇群，根據(jù)層次分解的方向可以將其分為凝聚層次聚類與分裂層次聚類兩種算法。凝聚層次聚類算法開始運行時將每個對象認為是一個簇，然后迭代地根據(jù)某種相似性度量尋找到兩個最接近的簇并將其合并成一個更大的簇，直到達到某指定條件或所有對象都聚集到一起；分裂層次聚類則相反，先將所有數(shù)據(jù)置于一個簇中，然后遞歸地將現(xiàn)有的簇分裂為更多的較小的簇，直到每個對象自成一簇或者達到用戶預(yù)設(shè)條件。

無論是凝聚的還是分裂的層次聚類算法都需要合理度量兩個簇之間的距離。首先，對象間的距離可以采用歐氏距離、曼哈頓距離以及余弦距離等，在每種對象間距離的基礎(chǔ)上，簇間距離又可以使用兩簇各對象間距離的最小、最大、平均值以及兩簇中心間的距離來衡量。對于歐氏距離，JrWard［19］提出了使用ESS（離差平方和）來輔助度量，合并兩簇的代價等于將兩者合并后整體數(shù)據(jù)中各簇離差平方和之和減去合并前的各簇離差平方和之和，該值越小說明合并這兩簇越能降低總體離散程度。

層次聚類算法可以通過設(shè)置不同的目標參數(shù)得到不同粒度上的多層次聚類結(jié)構(gòu)。在聚類形狀方面，層次聚類適用于任意形狀的聚類，且對樣本的輸入順序不敏感；但是層次聚類的缺點是不可逆，下一次分裂或凝聚都是在上一次的基礎(chǔ)上進行，因此錯誤會隨著迭代一直傳遞下去，此外，層次聚類的算法時間復(fù)雜度也較大。

1.3基于圖的聚類算法

基于圖的聚類算法將任意形狀數(shù)據(jù)集群的聚類轉(zhuǎn)換為圖劃分任務(wù)，SNN［20］和Chameleon［21］是該類兩種典型的算法。在SNN算法中，首先構(gòu)造相似度矩陣，再根據(jù)各對象間的共享近鄰來構(gòu)造近鄰圖，接著對圖中的邊進行過濾，將連接強度小于某給定閾值的邊去除，最后將每個連通子圖作為一個類簇返回。Chameleon算法首先在給定的數(shù)據(jù)集上構(gòu)建KNN（K-nearest neighbors）圖，然后使用hMETIS算法通過最小化截斷邊權(quán)重和的方式將近鄰圖分割為預(yù)設(shè)數(shù)量的子圖，最后通過一種度量選擇合并的子簇，該度量同時考慮了兩個子簇間的互聯(lián)性與相似性，而使用用戶設(shè)定的超參數(shù)可以調(diào)整對互連性或相似性的側(cè)重。上述兩種方法的時間復(fù)雜度都是O（n2），其中n是數(shù)據(jù)集中對象的個數(shù)。圖聚類算法的優(yōu)點是適用于任何形狀的數(shù)據(jù)集，但是例如SNN中篩去邊的閾值、Chameleon中KNN的K值等都是需要用戶去預(yù)設(shè)的，具有很強的不確定性。

1.4基于密度的聚類算法

基于密度的聚類算法將所有數(shù)據(jù)都投射到一個數(shù)據(jù)空間中，可以認為簇是空間中被稀疏區(qū)域分隔開的稠密區(qū)域，因此此類算法往往可以發(fā)現(xiàn)任意形狀的簇。實現(xiàn)過程中，對于一個簇，只要某鄰域中的對象密度超過設(shè)定的閾值，就將其吸收到自身中。DBSCAN［22］和DENCLUE［23］算法是該類型兩種典型的算法。DBSCAN算法使用用戶給定的參數(shù)來指定鄰域半徑，并迭代地將密度可達的對象都吸收到簇中，將領(lǐng)域?qū)ο竺芏刃∮陂撝档狞c設(shè)為離群點。DENCLUE算法基于密度分布函數(shù)，使用步進式爬山的方法尋找密度函數(shù)的局部最大點，如果該點密度大于給定閾值，就為密度吸引點，否則為離群點。最后通過確定哪些對象被這些密度吸引點吸引來確定簇。上述兩種方法對任意形狀的簇都有高效的發(fā)掘能力，但是對于超參數(shù)的值也很敏感。為了克服這一點，另一種基于密度的聚類算法［24］通過沿密度梯度的方向移動數(shù)據(jù)對象來收縮簇結(jié)構(gòu)，并從具有不同參數(shù)的多個執(zhí)行中選擇最佳的聚類結(jié)果，但代價是更高的時間復(fù)雜度。

1.5其他聚類算法

此外，還有聚類算法聚焦于稀有類的識別［25］、任意形狀類簇聚類［26，27］等。

上述所有聚類算法都有廣泛的應(yīng)用，其有效性也歷經(jīng)檢驗，但是它們并非為同源分析所提出。本文所做工作是使用模型擬合數(shù)據(jù)模擬傳播結(jié)果的生成過程，并判斷每條傳播結(jié)果的隸屬。雖然上述方法可以達到類似的結(jié)果，但是其拋開了問題本質(zhì)，只對結(jié)果進行相似性聚類，與本文問題背景結(jié)合不夠緊密，可解釋性不高。

2問題描述

在傳播結(jié)果同源分析的問題中，傳播網(wǎng)絡(luò)拓撲結(jié)構(gòu)可以認為是一個有向圖G=（V，E），其中V={vi}Ni=1是表示傳播網(wǎng)絡(luò)所有N個節(jié)點的點集，而E是表示節(jié)點之間存在潛在影響關(guān)系的有向邊的邊集，（vi，vj）∈E表明從節(jié)點vi到節(jié)點vj存在一條有向邊。假設(shè)一共記錄了L條傳播結(jié)果，每條傳播結(jié)果s（∈{1，…，L}）都是記錄了從K組源頭之一開始的一次傳播過程的0-1記錄向量，表示某一次傳播過程結(jié)束后，網(wǎng)絡(luò)中N個節(jié)點的感染狀態(tài)。本文主要研究如何將傳播結(jié)果集S進行聚類，使得來自于同一組源頭的傳播結(jié)果聚集到同一類中，具體問題可以描述如下：

給定傳播網(wǎng)絡(luò)G=（V，E）上起源于K組源頭的L次相互獨立的傳播過程形成的各節(jié)點感染狀態(tài)結(jié)果集S={s1，…，sL}，其中s={y1，…，yN}（∈{1，…，L}）表示第次傳播過程結(jié)束時各個節(jié)點最終感染狀態(tài)，yi∈{0，1}（1表示節(jié)點被感染，0表示節(jié)點未被感染）表示第條傳播結(jié)果中第i個節(jié)點vi的感染狀態(tài)。L條傳播結(jié)果各由起始于K組源頭之一的傳播過程產(chǎn)生，但是屬于哪組源頭未知。求得每條傳播結(jié)果所屬的同源類以及與其來自于同一源頭的傳播結(jié)果。

3伯努利混合模型求解同源分析問題

本文選擇具有K個子分布的N維伯努利混合模型來擬合每條傳播結(jié)果s的概率分布，原因有：a）s中每個節(jié)點的值服從伯努利分布，非0即1；b）傳播結(jié)果s是N維向量，因為它反映了網(wǎng)絡(luò)中N個節(jié)點最終的感染狀態(tài)；c）所有傳播結(jié)果都來自于K組源頭之一所產(chǎn)生的傳播過程，因此需要K個分量去擬合不同源頭的傳播行為。如果能夠求得每條傳播結(jié)果屬于各個伯努利分量的概率，就能將其分配到概率最大的分量對應(yīng)的同源類，因此，可以將同源分析問題轉(zhuǎn)換為伯努利混合模型的求解問題。

本章首先介紹了伯努利混合模型以及該模型各參數(shù)在本文具體問題下的含義；然后介紹了基于伯努利混合模型和觀測數(shù)據(jù)構(gòu)建的對數(shù)似然函數(shù)及其參數(shù)的迭代求解過程；接著討論伯努利參數(shù)的初始化方式；最后對所提算法進行總結(jié)和時間復(fù)雜度分析。

3.1伯努利混合模型

為了簡潔、直接地反映和模擬傳播結(jié)果集S，將每條傳播結(jié)果視為一個單元，并對該結(jié)果中每個節(jié)點感染狀態(tài)的概率分布進行建模，該模型可以描述如下：

p（s|μ，π） = ∑Kk=1πkNi=1 μyi

ki（1-μki）1-yi（1）

其中：π={π1，…，πK}，πk是第k個伯努利分量權(quán)重系數(shù)，且滿足∑Kk=1πk=1；μ={μ1，…，μK}，μk是第k個伯努利分量的伯努利參數(shù)，且μk={μk1，…，μkN}，μki表示第k個伯努利分量的第i維度的參數(shù)。

在該模型中，每條傳播結(jié)果s（∈{1，…，L}）都被認為是由一個伯努利分量生成的。假設(shè)其對應(yīng)的伯努利參數(shù)為μk，則p（yi=1|μk）=μki表示s由第k個伯努利分量生成時第i個節(jié)點最終狀態(tài)為1的概率是μki。如果有一組傳播結(jié)果來自于同一組源頭產(chǎn)生的傳播過程，則認為它們也傾向于由同一個伯努利分量生成，且該伯努利分量對應(yīng)的權(quán)重系數(shù)πk反映了這組傳播結(jié)果所屬同源類在整個數(shù)據(jù)集中的權(quán)重，也可視為先驗概率。

為了得到每條傳播結(jié)果屬于哪個同源類，設(shè)置變量Z={z1，…，zL}，其中z={z1，…，zK}（∈{1，…，L}）是一個K維向量，且只有一個元素等于1，其他元素等于0。zk=1表示第條傳播結(jié)果s是由伯努利混合模型的第k個分量生成的。設(shè)hk=E［zk］，它反映了該傳播結(jié)果屬于第k個伯努利分量的期望。根據(jù)貝葉斯定理，可以推導(dǎo)出hk的表達式為

hk=p（zk=1|s）=

p（s|zk=1）p（zk=1）∑Km=1p（s|zm=1）p（zm=1）=πkp（s|μk）∑Km=1πmp（s|μm）（2）

其中：p（s|μk）表示第條傳播結(jié)果s由第k個伯努利分量生成時的后驗概率。對于網(wǎng)絡(luò)中的第i個節(jié)點，在結(jié)果序列中狀態(tài)為1的概率就是μki，而狀態(tài)為0的概率為1-μki。由于多維伯努利分布各維間獨立分布，總概率就是傳播結(jié)果中各節(jié)點的概率之積，最后可以寫成一個統(tǒng)一的表達式，即

p（s|μk）=Ni=1μyiki（1-μki）1-yi（3）

3.2參數(shù)估計

基于上述的伯努利混合模型，本文采用最大似然的方法根據(jù)傳播結(jié)果數(shù)據(jù)集S來估計模型參數(shù)π和μ。

首先寫出具有K個子分布的N維伯努利混合模型的對數(shù)似然函數(shù)：

log L（S|μ，π）=∑L=1log ∑Kk=1πkNi=1μyiki（1-μki ）1-yi（4）

接著使用EM（expectation-maximum）算法，即期望最大化算法來求解。EM算法是一種迭代優(yōu)化的策略，它的每一次迭代都分兩步，第一步為期望步（E步），即通過上一輪的結(jié)果估計如變量zk的期望hk；第二步為極大步（M步），即根據(jù)上一步估計出的變量值結(jié)合已知數(shù)據(jù)，通過極大似然去估計如π和μ的模型參數(shù)值。因此可以通過極大步（M步）去極大似然函數(shù)以實現(xiàn)對π和μ的值的更新。對于μ，讓伯努利混合模型的對數(shù)似然函數(shù)對μki求導(dǎo)，并令導(dǎo)數(shù)為0。

log L（S|μ，π）μki=∑L=1μkilog ∑Km=1πmNn=1 μyn

mn（1-μmn）1-yn=

∑L=1hkμki log （μyi

ki（1-μki）1-yi）=∑L=1hi（yiμki-1-yi1-μki）=0（5）

可求得

μki=∑L=1hkyi∑L=1hk，μk=∑L=1hks∑L=1hk（6）

為了求解π，考慮到∑Kk=1πk=1的約束，先構(gòu)造拉格朗日函數(shù)：

L（π，λ）=log L（S|μ，π）+λ（1-∑Kk=1πk）（7）

然后利用KKT條件可得

πkL（π，λ）=1πk∑L=1hk-λ=0（8）

所以∑L=1hk=λπk，令Lk=∑L=1hk，再由∑Kk=1πk=1可得

∑Kk=1∑L=1hk=∑Kk=1Lk=λ∑Kk=1πk=λ

最終可得πk的表達式為

πk=1λ∑L=1hk=Lk∑Kk=1Lk（9）

根據(jù)獲取的參數(shù)更新公式，得到參數(shù)估計的步驟為：首先初始化模型參數(shù)π和μ，然后根據(jù)式（2）估算每一條傳播結(jié)果屬于各同源類的期望，接著分別根據(jù)式（6）（9）更新每個同源類k對應(yīng)伯努利分量的伯努利參數(shù)μk和該分量對應(yīng)的權(quán)重系數(shù)πk，交替更新過程直至兩次更新后參數(shù)的差異小于預(yù)設(shè)閾值，模型收斂，迭代更新結(jié)束，得到最終參數(shù)估計值。最后根據(jù)收斂后獲得的h={h1，…，hK}確定每條傳播結(jié)果s所屬同源類，所屬類使得hk最大。

3.3參數(shù)的初始化

除了給定的數(shù)據(jù)集S以及K值，伯努利混合模型主要由兩個重要參數(shù)，即3.2節(jié)中計算的π和μ。以下討論如何初始化上述參數(shù)以達到減少迭代次數(shù)、提高準確率等效果。

1）μ的初始化

本文使用Ward-linkage層次聚類先將數(shù)據(jù)集S聚類成K類，再用它們分別去初始化伯努利混合模型各分量的均值參數(shù)μ={μ1，…，μK}。Ward-linkage層次聚類采用自低而上的凝聚式方法，首先讓每條傳播結(jié)果自成一類，然后通過最小化離差平方和（error sum of squares，ESS）增量的方式合并當前的類簇，直到系統(tǒng)中只剩余K類。對于某類k，其離差平方和ESS（k） 計算公式如下：

ESS（k）=∑nki=1‖si‖2-1nk‖∑nki=1si‖2（10）

其中：nk為該類中傳播結(jié)果的條數(shù)；si為該類中的第i（i=1，…，nk）條傳播結(jié)果。

如果系統(tǒng)中當前共有m個類簇，那么系統(tǒng)的總離差平方和為

ESS（total）=∑mk=1ESS（k）（11）

合并兩類i和j為iamp;j的代價D（i，j）是合并后系統(tǒng)的總離差平方和減去合并前系統(tǒng)的總離差平方和，即

D（i，j）=ESS（iamp;j）-ESS（i）-ESS（j）（12）

根據(jù)Lance-Williams算法，代價可以使用遞推的方式計算：

D（k，iamp;j）=ni+nkni+nj+nkD（k，i）+

nj+nkni+nj+nkD（k，j）-nkni+nj+nkD（i，j）（13）

為了降低時間復(fù)雜度，本文使用一個最小堆來存儲類對的信息和合并代價，每輪迭代只需取出堆頂對象，將其中包含的兩類合并。接著根據(jù)式（13）計算新產(chǎn)生的類與系統(tǒng)中其他各類的合并代價并插入最小堆中。重復(fù)上述過程，直到系統(tǒng)中只剩下K類。最后使用K類中每個簇里各節(jié)點為1的概率來初始化相應(yīng)伯努利參數(shù)，即

μk=1nk∑nki=1si（14）

用上述方法初始化參數(shù)μ可以避免隨機初始化帶來的不確定性以及準確率的波動，能有效減少伯努利混合模型的迭代次數(shù)并提高準確率，但是預(yù)處理也帶來了一定額外的時間復(fù)雜度。

2）π的初始化

參數(shù)π反映了各伯努利分量所占權(quán)重，或者說是各分量的先驗概率。由式（9）可知，其可以看做軟劃分情況下各分量產(chǎn)生的傳播結(jié)果占總傳播結(jié)果數(shù)量的比例。本文繼續(xù)使用Ward-linkage層次聚類的結(jié)果來初始化其值，即πk的值等于層次聚類后第k類中傳播結(jié)果的個數(shù)除以傳播結(jié)果總數(shù)。用該方法初始化π相對于隨機初始化或者用同一個數(shù)初始化，可以在一定程度上使得各分量先驗概率更接近真實值，從而有效減少迭代次數(shù)。在遇到數(shù)據(jù)集中產(chǎn)生自各組源頭的傳播結(jié)果數(shù)量差異較大的情況時，該方法能夠使模型更快收斂，更容易達到全局最優(yōu)。

3.4算法總結(jié)

本文研究了如何對記錄了節(jié)點最終感染狀態(tài)的傳播結(jié)果數(shù)據(jù)集進行同源分析，這些傳播結(jié)果記錄的傳播過程產(chǎn)生于若干組不同源頭中的某一組，本文通過高效的算法實現(xiàn)了將來自于同一組源頭的傳播結(jié)果聚類到一起。本文選擇具有K個子分布的N維伯努利混合模型來擬合傳播結(jié)果，其中K取決于已知的不同源頭的組數(shù)，N取決于傳播網(wǎng)絡(luò)中節(jié)點的個數(shù)。建立好模型并適當?shù)爻跏蓟螅疚牟捎肊M算法對模型進行迭代求解，最終在模型參數(shù)收斂后從參數(shù)中計算得到每條傳播結(jié)果所屬的同源類編號。

本文算法時間復(fù)雜度主要在于預(yù)處理和伯努利混合擬合的過程。預(yù)處理過程中，首先計算所有傳播結(jié)果兩兩間的距離矩陣，時間復(fù)雜度是O（L2N），其中L為傳播結(jié)果數(shù)量，N為傳播網(wǎng)絡(luò)中節(jié)點的個數(shù)。接著開始迭代凝聚：a）由于維護了最小堆，所以尋找距離最近的兩個簇的時間復(fù)雜度是O（1）；b）計算合并后的新簇到所有簇間的距離并插入最小堆，需要O（L log L）的時間復(fù)雜度。因為目標類數(shù)是K，所以迭代輪數(shù)為L-K，于是預(yù)處理的總時間復(fù)雜度O（L2N+（L-K）L log L）。伯努利混合模型擬合過程中，每一輪迭代主要由兩部分組成：a）對每條傳播結(jié)果進行同源類劃分，計算每條結(jié)果產(chǎn)生于某個伯努利分量的概率的時間復(fù)雜度為O（N），其中N為傳播網(wǎng)絡(luò)中節(jié)點的個數(shù)，因為共有L條傳播結(jié)果，且有K個伯努利分量，所以第一步同源類劃分的時間復(fù)雜度為O（LKN）；b）更新伯努利混合模型的參數(shù)，對于第k個伯努利分量，計算Lk需要的時間復(fù)雜度為O（L），而更新μk的復(fù)雜度為O（LN），所以更新參數(shù)μ={μ1，…，μK}的時間復(fù)雜度為O（LKN），更新π={π1，…，πK}的時間復(fù)雜度為O（K）。于是第二步的時間復(fù)雜度就是O（LKN）。所以每一輪迭代過程的時間復(fù)雜度也是O（LKN）。假設(shè)模型一共迭代了t輪，伯努利混合模型所需總時間復(fù)雜度為O（tLKN）。綜上，本文算法總時間復(fù)雜度為O（L2N+（L-K）L log L+tLKN），其運行時間主要取決于伯努利混合模型迭代輪數(shù)、網(wǎng)絡(luò)大小、收集的傳播結(jié)果數(shù)量以及源頭的組數(shù)。

4實驗與結(jié)果

4.1實驗設(shè)置

1）數(shù)據(jù)集

a）傳播網(wǎng)絡(luò)的生成。采用人工合成的LFR網(wǎng)絡(luò)［28］來生成加權(quán)有向圖進行實驗，對于LFR網(wǎng)絡(luò)，通過改變網(wǎng)絡(luò)節(jié)點個數(shù)N和網(wǎng)絡(luò)節(jié)點度的平均值D來生成兩個系列的網(wǎng)絡(luò)，其對應(yīng)的屬性匯總在表1中。對于邊的權(quán)值，即傳播過程中的感染傳播概率，使其服從均值為0.3、方差為0.05的高斯分布，這使得95%以上的概率值分布在0.2～0.4。

b）傳播結(jié)果數(shù)據(jù)集S的生成。在實驗的人工網(wǎng)絡(luò)上通過模擬多次感染爆發(fā)過程來生成感染數(shù)據(jù)。假設(shè)一共有K組源頭，對于每個源頭，模擬生成β條傳播結(jié)果。在每一次模擬感染傳播的過程中先挑選一部分節(jié)點作為初始感染點，其占據(jù)節(jié)點總數(shù)的比例為，然后根據(jù)獨立級聯(lián)模型進行模擬傳播，記錄傳播網(wǎng)絡(luò)結(jié)束后各個節(jié)點的感染狀態(tài)作為實驗數(shù)據(jù)。

2）評價指標

對于實驗結(jié)果的評估，采用歸一化互信息（NMI）作為評價指標，其反映的是一個隨機變量里包含的關(guān)于另一個隨機變量的信息量，或者說是兩個隨機變量的相關(guān)度。假設(shè)X和Y分別是所有傳播結(jié)果的預(yù)測同源類序號和真實同源類序號，概率密度分布分別是p（x）和p（y），聯(lián)合分布為p（x，y），可求得X和Y的互信息為

I（X，Y）=∑x∈X，y∈Y p（x，y） log p（x，y）p（x）p（y）（15）

將其歸一化，首先分別計算X和Y的熵為

H（X）=-∑x∈X p（x） log p（x）

H（Y）=-∑y∈Y p（y） log p（y）（16）

最終就可以得到歸一化互信息的表達式：

NMI（X，Y）=I（X，Y）（H（X）+H（Y））/2（17）

3）對比算法

本文將伯努利混合模型分別與層次聚類算法、K-means算法以及RSC算法［29］在通過改變七個參數(shù)而生成的多個數(shù)據(jù)集上進行比較。其中，K-means算法的迭代過程與本文算法有些許類似：K-means算法使用對象到類中心的距離來劃分對象，并根據(jù)劃分結(jié)果更新中心點；而本文算法根據(jù)對象在伯努利各分量上的生成概率來計算對象隸屬于各分量的概率以實現(xiàn)軟劃分，進而根據(jù)劃分結(jié)果更新伯努利參數(shù)。為了對比全面，K-means算法和層次聚類算法都分別使用歐拉距離、曼哈頓距離以及余弦距離三種距離計算方式。而層次聚類又分別使用兩類間各組向量距離的最大、最小和平均作為兩類間距離的代表。此外，RSC算法基于一個假設(shè)，即兩個距離最近的數(shù)據(jù)點應(yīng)該分組在一個集群中，所以它對于每個未劃分的節(jié)點，將其鏈接到其最近的鄰居，而該鄰居又會進一步與自身最近的鄰居相連，依次類推形成一條節(jié)點鏈，直到滿足終止條件，然后將該節(jié)點作為一個子聚類樹或加入到現(xiàn)有的子聚類樹中，再以子聚類樹為單位繼續(xù)迭代地構(gòu)造更高層次的聚類樹。對于上述所有算法，本文都提供了與預(yù)處理伯努利混合模型一樣的輸入，各自輸出預(yù)測類標簽，比較它們的NMI。

4.2傳播網(wǎng)絡(luò)大小N的影響

為研究傳播網(wǎng)絡(luò)大小對算法性能的影響，在LFR1～5上對算法進行了測試（K=4，β=70，=0.2）。表2展示了各算法同源聚類的準確性，即NMI的值，其中Bernoulli代表本文算法，即進行了預(yù)處理的伯努利混合模型算法。

從表2中可以看出，預(yù)處理伯努利混合模型的NMI普遍高于其他對比算法。當傳播網(wǎng)絡(luò)規(guī)模減小時，各層次聚類算法的準確性有明顯下降趨勢；而本文算法幾乎不受影響，當網(wǎng)絡(luò)節(jié)點個數(shù)減小到200，還保持著100%的準確率，節(jié)點個數(shù)為100時才有輕微下降，但是下降幅度微乎其微。原因是當網(wǎng)絡(luò)規(guī)模減小時，各傳播結(jié)果所含的信息量減少，由于與問題背景和數(shù)據(jù)特征結(jié)合不緊密，對比算法此時難以精確區(qū)分，且層次聚類過程中的錯誤由于其不可逆性而不斷累積，導(dǎo)致準確性降低。但是伯努利混合模型由于與問題背景結(jié)合更緊密，對數(shù)據(jù)特征的利用率也更高，所以對信息更加敏感；再加上其通過迭代可以糾正之前的錯誤，所以伯努利混合模型效果遠超其他算法。

4.3傳播網(wǎng)絡(luò)平均度D的影響

為研究傳播網(wǎng)絡(luò)平均度對算法性能的影響，在LFR6～10上對各算法分別進行了測試（K= 4，β= 70，=0.2）。LFR6～10各網(wǎng)絡(luò)對應(yīng)的網(wǎng)絡(luò)平均度分別為3、4、5、6、7。表3展示了各算法在五種情況下同源聚類的準確性。

從表3中可以看出，隨著節(jié)點度的平均值增大，所有對比算法的準確率都在不斷降低，D到達7后，對比算法的準確率呈現(xiàn)斷崖式下跌。而本文算法在平均度升高到6都未受到影響，之后雖然準確率也有所下降，但是下降幅度很小，較其他算法有顯著優(yōu)勢。原因是隨著網(wǎng)絡(luò)平均度增大，復(fù)雜度提高，同一組源頭產(chǎn)生的傳播結(jié)果間都會有很大差異，離群點數(shù)量也會相應(yīng)大大增加。各算法每次迭代的準確性相應(yīng)降低，層次聚類由于其不可逆性，錯誤不斷累積，導(dǎo)致最后準確性極低；而K-means算法由于對離群點非常敏感，準確率下降也很大。但伯努利混合模型能夠在迭代過程中更新劃分糾正錯誤，并且與K-means不同，其采用軟劃分，離群點的影響被各簇分攤，避免了對某簇產(chǎn)生嚴重的影響，所以效果顯著領(lǐng)先。

4.4源頭組數(shù)K的影響

為研究源頭組數(shù)對算法性能的影響，在LFR3上對算法進行了測試（β=70，=0.2），五個數(shù)據(jù)集對應(yīng)的同源類個數(shù)分別為2、3、4、5、6。表4展示了各算法在不同組數(shù)下同源聚類的準確性。從表4結(jié)果中可以看出，隨著源頭組數(shù)的增多，部分算法效率逐漸降低，部分算法準確率受到的影響不大，但是伯努利混合模型在所有情況下都保持100%正確率，遠優(yōu)于對比算法。

4.5每組源頭產(chǎn)生傳播結(jié)果數(shù)β的影響

為研究每組源頭產(chǎn)生的傳播結(jié)果數(shù)對算法性能的影響，在LFR3上對算法進行了測試（K=4，=0.2），五個數(shù)據(jù)集對應(yīng)的β分別為40、55、70、85、100。表5展示了各算法在不同β下同源聚類的準確性。

從表5中可以看出，隨著β的降低，數(shù)據(jù)集中可用信息量減少，各傳播結(jié)果數(shù)據(jù)分布的隨機性也增大。所有對比算法的準確率均有所下降，但是伯努利混合模型受其影響不大，只有輕微波動，所有情況下都有極優(yōu)的表現(xiàn)。

4.6初始感染節(jié)點所占比例的影響

為研究源頭節(jié)點占總節(jié)點個數(shù)比例對算法性能的影響，在LFR3上對算法進行了測試（K=4，β=70），五個數(shù)據(jù)集對應(yīng)的分別為0.1、0.15、0.2、0.25、0.3。表6展示了各算法在不同下同源聚類的準確性。

從表6的結(jié)果中可以看出，隨著的降低，所有對比算法的準確率均呈顯著下降趨勢，而本文算法一直保持著極高的準確率。

4.7每組源頭產(chǎn)生傳播結(jié)果數(shù)不平衡度的影響

為了研究在不同源頭產(chǎn)生的傳播結(jié)果數(shù)量不一致的情況下算法的表現(xiàn)，在LFR3上對算法進行了測試（K=4，=0.2），所有數(shù)據(jù)集中β的均值皆為70，設(shè)4組源頭生成的傳播結(jié)果數(shù)量為一個等差數(shù)列，且令公差分別為0、10、20、30、40。表7展示了各算法在不同公差下同源聚類的準確性。

從表7結(jié)果中可以看出，隨著不平衡度上升，K-means算法的準確率呈下降趨勢，層次聚類也只保持在較低水平，而本文算法在公差到達40前均不受影響，保持100%的準確率，接著才略微有一些輕微下降。原因是K-means算法初始化時，假設(shè)各個類的先驗概率相同且初始化有隨機性，后續(xù)迭代就可能陷入局部最優(yōu)解；但本文算法先通過預(yù)處理確定了各類的先驗概率，然后在迭代過程中，一方面擁有對象更少的類對應(yīng)的權(quán)重π更小，另一方面各對象屬于權(quán)重π更小的伯努利分量的概率也相對更小。因此本文算法收斂更快，更接近全局最優(yōu)。

4.8初始感染節(jié)點所占比例不平衡度的影響

為了研究在每組源頭中節(jié)點數(shù)量不一致的情況下算法的表現(xiàn)，在LFR3上對算法進行了測試（K=4，β=70），所有數(shù)據(jù)集中的均值皆為0.2，將 4組源頭節(jié)點的數(shù)量占總節(jié)點數(shù)的比例設(shè)置為一個等差數(shù)列，且令公差分別為0、0.03、0.06、0.09、0.12。表8展示了各算法在不同公差下同源聚類的準確性。

從表8結(jié)果中可以看出，隨著公差增大，不平衡度上升，大部分算法準確率均在某個值附近波動，而伯努利混合算法的準確率一直遠高于其他對比算法。

4.9預(yù)處理的影響

為研究預(yù)處理對算法結(jié)果產(chǎn)生的影響，本文在LFR3上對算法進行了測試（K=4，β=70，=0.2）。由于若不進行預(yù)處理，算法會有一定的隨機性，所以在普通伯努利混合模型運行了10次，并記錄相應(yīng)結(jié)果。表9展示了不加預(yù)處理與添加預(yù)處理兩種情況下同源聚類的迭代次數(shù)和準確性。

此外，未經(jīng)過預(yù)處理的伯努利混合模型最少迭代次數(shù)為6，最多迭代次數(shù)為12。從表9中可以看出，使用了預(yù)處理的伯努利混合模型不僅迭代次數(shù)大大減少（不僅少于非預(yù)處理模型的平均迭代次數(shù)，還少于其最少迭代次數(shù)），而且準確率有所提升。經(jīng)過實驗驗證，在調(diào)整參數(shù)后的其他情況下，也有類似的效果。可見預(yù)處理能夠降低隨機性，提高算法綜合表現(xiàn)。

5結(jié)束語

本文研究了傳播結(jié)果同源分析問題，使用伯努利混合模型對大量傳播過程結(jié)束后觀察到的最終節(jié)點感染狀態(tài)數(shù)據(jù)進行擬合。模型的每個分量對應(yīng)一組傳播源頭，其描述了一組源頭產(chǎn)生的影響在網(wǎng)絡(luò)中各節(jié)點的到達概率，并由此實現(xiàn)將產(chǎn)生自同一組源頭的傳播結(jié)果聚類，從而為后續(xù)的溯源等工作奠基。模型使用EM算法迭代收斂，并通過Ward-linkage層次聚類算法進行預(yù)處理以減少迭代次數(shù)，提高準確率。本文使用大量實驗對算法的準確性和穩(wěn)定性進行評估，證明了本文算法能夠高效準確地實現(xiàn)傳播結(jié)果同源分析工作。

未來，基于同源分析的工作能夠得到更豐富的傳播結(jié)果數(shù)據(jù)和樣本可以進一步進行傳播源頭的追溯，傳播網(wǎng)絡(luò)拓撲結(jié)構(gòu)推斷以及影響最大化等研究工作。

參考文獻：

［1］Li Weizhong，Jaroszewski L，Godzik A.Clustering of highly homologous sequences to reduce the size of large protein databases［J］.Bioinformatics，2001，17（3）：282-283.

［2］Chan C X，Mahbob M，Ragan M A.Clustering evolving proteins into homologous families［J］.BMC Bioinformatics，2013，14（1）：article No.120.

［3］Balaban M，Moshiri N，Mai U，et al.TreeCluster：clustering biological sequences using phylogenetic trees［J］.PLoS One，2019，14（8）：e0221068.

［4］He Xinran，Rekatsinas T，F(xiàn)oulds J，et al.Hawkestopic：a joint model for network inference and topic modeling from text-based cascades［C］//Proc of the 32nd International Conference on Machine Learning.2015：871-880.

［5］Wallinga J，Teunis P.Different epidemic curves for severe acute respiratory syndrome reveal similar impacts of control measures［J］.American Journal of Epidemiology，2004，160（6）：509-516.

［6］張平，王黎維，彭智勇，等.一種面向團體的影響最大化方法［J］.軟件學(xué)報，2017，8（8）：2161-2174.（Zhang Ping，Wang Liwei，Peng Zhiyong，et al.Group-based method for influence maximization［J］.Journal of Software，2017，8（8）：2161-2174.）

［7］Yan Qian，Huang Hao，Gao Yunjun，et al.Group-level influence maximization with budget constraint［C］//Proc of the 22nd International Conference on Database Systems for Advanced Applications.Cham：Springer，2017：625-641.

［8］Huang Hao，Yan Qian，Gan Ting，et al.Learning diffusions without timestamps［C］//Proc of the 33rd AAAI Conference on Artificial Intelligence.Palo Alto，CA：AAAI Press，2019：582-589.

［9］孫月明，張運加，顏錢，等.無須感染時間信息的傳播網(wǎng)絡(luò)快速推斷算法［J］.計算機科學(xué)與探索，2019，13（4）：541-553.（Sun Yueming，Zhang Yunjia，Yan Qian，et al.Fast inference algorithm of diffusion networks without infection temporal information［J］.Journal of Frontiers of Computer Science amp; Technology，2019，13（4）：541-553.）

［10］Han Keqi，Tian Yuan，Zhang Yunjia，et al.Statistical estimation of diffusion network topologies［C］//Proc of the 36th IEEE International Confe-rence on Data Engineering.Piscataway，NJ：IEEE Press，2020：625-636.

［11］Huang Hao，Yan Qian，Chen Lu，et al.Statistical inference of diffusion networks［J］.IEEE Trans on Knowledge and Data Engineering，2021，33（2）：742-753.

［12］Gan Ting，Han Keqi，Huang Hao，et al.Diffusion network inference from partial observations［C］//Proc of the 35th AAAI Conference on Artificial Intelligence.Palo Alto，CA：AAAI Press，2021：7493-7500.

［13］趙姝，劉曉曼，段震，等.社交關(guān)系挖掘研究綜述［J］.計算機學(xué)報，2017，40（3）：535-555.（Zhao Shu，Liu Xiaoman，Duan Zhen，et al.Survey on social ties mining［J］.Chinese Journal of Compu-ters，2017，40（3）：535-555.）

［14］MacQueen J.Some methods for classification and analysis of multiva-riate observations［C］//Proc of the 5th Berkeley Symposium on Mathematical Statistics and Probability.Berkeley，CA：University of California Press，1967：281-297.

［15］Park H S，Jun C H.A simple and fast algorithm for K-medoids clustering［J］.Expert Systems with Applications，2009，36（2）：3336-3341.

［16］Meng Yinfeng，Liang Jiye，Cao Fuyuan，et al.A new distance with derivative information for functional K-means clustering algorithm［J］.Information Sciences，2018，463-464（10）：166-185.

［17］Sinaga K P，Yang M S.Unsupervised K-means clustering algorithm［J］.IEEE Access，2020，8：80716-80727.

［18］Schubert E，Rousseeuw P J.Faster K-medoids clustering：improving the PAM，CLARA，and CLARANS algorithms［C］//Proc of the 12th International Conference on Similarity Search and Applications.Cham：Springer，2019：171-187.

［19］Jr Ward J H.Hierarchical grouping to optimize an objective function［J］.Journal of the American Statistical Association，1963，58（301）：236-244.

［20］Ertz L，Steinbach M，Kumar V.Finding clusters of different sizes，shapes，and densities in noisy，high dimensional data［C］//Proc of SIAM International Conference on Data Mining.2003：47-58.

［21］Karypis G，Han E H，Kumar V.Chameleon：hierarchical clustering using dynamic modeling［J］.Computer，1999，32（8）：68-75.

［22］Ester M，Kriegel H P，Sander J，et al.A density-based algorithm for discovering clusters in large spatial databases with noise［C］//Proc of the 2nd International Conference on Knowledge Discovery and Data Mining.Palo Alto，CA：AAAI Press，1996：226-231.

［23］Hinneburg A，Keim D A.An efficient approach to clustering in large multimedia databases with noise［C］//Proc of the 4th International Conference on Knowledge Discovery and Data Mining.Palo Alto，CA：AAAI Press，1998：58-65.

［24］Shi Yong，Song Yuqing，Zhang Aidong.A shrinking-based approach for multi-dimensional data analysis［C］//Proc of the 29th Annual International Conference on Very Large Data Bases.［S.l.］：VLDB Endowment，2003：440-451.

［25］Huang Hao，Yan Qian，Lu Wei，et al.LERI：local exploration for rare-category identification［J］.IEEE Trans on Knowledge and Data Engineering，2019，32（9）：1761-1772.

［26］Huang Hao，Gao Yunjun，Chiew K，et al.Towards effective and efficient mining of arbitrary shaped clusters［C］//Proc of the 30th IEEE International Conference on Data Engineering.Piscataway，NJ：IEEE Press，2014：28-39.

［27］Huang Hao，Wang Song，Wu Shuangke，et al.Mining arbitrary shaped clusters and outputting a high quality dendrogram［C］//Proc of the 27th International Conference on Database and Expert Systems Applications.Cham：Springer，2016：153-168.

［28］Lancichinetti A，F(xiàn)ortunato S，Radicchi F.Benchmark graphs for testing community detection algorithms［J］.Physical Review E，2008，78（4）：046110.

［29］Xie Wenbo，Lee Yanli，Wang Cong，et al.Hierarchical clustering supported by reciprocal nearest neighbors［J］.Information Sciences，2020，527（7）：279-292.

收稿日期：2022-03-19；修回日期：2022-05-23基金項目：國家自然科學(xué)基金資助項目（61976163）；浙江省博士后基金資助項目（ZJ2021017）

作者簡介：楊旋（1983-），男，浙江杭州人，工程師，碩士，主要研究方向為醫(yī)學(xué)人工智能；徐貝澄（2001-），男，江蘇泰州人，本科，主要研究方向為數(shù)據(jù)挖掘；姚暢（1990-），男，重慶黔江人，高級工程師，博士，主要研究方向為醫(yī)學(xué)人工智能、信息檢索；黃浩（1986-），男（通信作者），湖北潛江人，教授，博導(dǎo)，博士，主要研究方向為數(shù)據(jù)庫、數(shù)據(jù)挖掘（haohuang@whu.edu.cn）.