傳播結果的同源分析

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

關鍵詞：傳播網絡；同源分析；伯努利混合模型；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引言

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

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

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

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

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

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

1相關工作

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

1.1基于劃分的聚類算法

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

1.2基于層次的聚類算法

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

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

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

1.3基于圖的聚類算法

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

1.4基于密度的聚類算法

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

1.5其他聚類算法

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

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

2問題描述

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

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

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

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

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

3.1伯努利混合模型

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

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

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

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

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

為了得到每條傳播結果屬于哪個同源類，設置變量Z={z1，…，zL}，其中z={z1，…，zK}（∈{1，…，L}）是一個K維向量，且只有一個元素等于1，其他元素等于0。zk=1表示第條傳播結果s是由伯努利混合模型的第k個分量生成的。設hk=E［zk］，它反映了該傳播結果屬于第k個伯努利分量的期望。根據貝葉斯定理，可以推導出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）表示第條傳播結果s由第k個伯努利分量生成時的后驗概率。對于網絡中的第i個節點，在結果序列中狀態為1的概率就是μki，而狀態為0的概率為1-μki。由于多維伯努利分布各維間獨立分布，總概率就是傳播結果中各節點的概率之積，最后可以寫成一個統一的表達式，即

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

3.2參數估計

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

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

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

接著使用EM（expectation-maximum）算法，即期望最大化算法來求解。EM算法是一種迭代優化的策略，它的每一次迭代都分兩步，第一步為期望步（E步），即通過上一輪的結果估計如變量zk的期望hk；第二步為極大步（M步），即根據上一步估計出的變量值結合已知數據，通過極大似然去估計如π和μ的模型參數值。因此可以通過極大步（M步）去極大似然函數以實現對π和μ的值的更新。對于μ，讓伯努利混合模型的對數似然函數對μki求導，并令導數為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的約束，先構造拉格朗日函數：

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）

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

3.3參數的初始化

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

1）μ的初始化

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

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

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

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

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

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

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

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

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

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

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

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

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

2）π的初始化

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

3.4算法總結

本文研究了如何對記錄了節點最終感染狀態的傳播結果數據集進行同源分析，這些傳播結果記錄的傳播過程產生于若干組不同源頭中的某一組，本文通過高效的算法實現了將來自于同一組源頭的傳播結果聚類到一起。本文選擇具有K個子分布的N維伯努利混合模型來擬合傳播結果，其中K取決于已知的不同源頭的組數，N取決于傳播網絡中節點的個數。建立好模型并適當地初始化之后，本文采用EM算法對模型進行迭代求解，最終在模型參數收斂后從參數中計算得到每條傳播結果所屬的同源類編號。

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

4實驗與結果

4.1實驗設置

1）數據集

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

b）傳播結果數據集S的生成。在實驗的人工網絡上通過模擬多次感染爆發過程來生成感染數據。假設一共有K組源頭，對于每個源頭，模擬生成β條傳播結果。在每一次模擬感染傳播的過程中先挑選一部分節點作為初始感染點，其占據節點總數的比例為，然后根據獨立級聯模型進行模擬傳播，記錄傳播網絡結束后各個節點的感染狀態作為實驗數據。

2）評價指標

對于實驗結果的評估，采用歸一化互信息（NMI）作為評價指標，其反映的是一個隨機變量里包含的關于另一個隨機變量的信息量，或者說是兩個隨機變量的相關度。假設X和Y分別是所有傳播結果的預測同源類序號和真實同源類序號，概率密度分布分別是p（x）和p（y），聯合分布為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］在通過改變七個參數而生成的多個數據集上進行比較。其中，K-means算法的迭代過程與本文算法有些許類似：K-means算法使用對象到類中心的距離來劃分對象，并根據劃分結果更新中心點；而本文算法根據對象在伯努利各分量上的生成概率來計算對象隸屬于各分量的概率以實現軟劃分，進而根據劃分結果更新伯努利參數。為了對比全面，K-means算法和層次聚類算法都分別使用歐拉距離、曼哈頓距離以及余弦距離三種距離計算方式。而層次聚類又分別使用兩類間各組向量距離的最大、最小和平均作為兩類間距離的代表。此外，RSC算法基于一個假設，即兩個距離最近的數據點應該分組在一個集群中，所以它對于每個未劃分的節點，將其鏈接到其最近的鄰居，而該鄰居又會進一步與自身最近的鄰居相連，依次類推形成一條節點鏈，直到滿足終止條件，然后將該節點作為一個子聚類樹或加入到現有的子聚類樹中，再以子聚類樹為單位繼續迭代地構造更高層次的聚類樹。對于上述所有算法，本文都提供了與預處理伯努利混合模型一樣的輸入，各自輸出預測類標簽，比較它們的NMI。

4.2傳播網絡大小N的影響

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

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

4.3傳播網絡平均度D的影響

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

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

4.4源頭組數K的影響

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

4.5每組源頭產生傳播結果數β的影響

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

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

4.6初始感染節點所占比例的影響

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

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

4.7每組源頭產生傳播結果數不平衡度的影響

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

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

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

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

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

4.9預處理的影響

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

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

5結束語

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

未來，基于同源分析的工作能夠得到更豐富的傳播結果數據和樣本可以進一步進行傳播源頭的追溯，傳播網絡拓撲結構推斷以及影響最大化等研究工作。

參考文獻：

［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，Foulds 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］.軟件學報，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］孫月明，張運加，顏錢，等.無須感染時間信息的傳播網絡快速推斷算法［J］.計算機科學與探索，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］趙姝，劉曉曼，段震，等.社交關系挖掘研究綜述［J］.計算機學報，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，Fortunato 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基金項目：國家自然科學基金資助項目（61976163）；浙江省博士后基金資助項目（ZJ2021017）

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