導語：自用的論文筆記

Su S, Guan J, Chen B, et al. Nonnegative Matrix Factorization Based on Node Centrality for Community Detection[J]. ACM Transactions on Knowledge Discovery from Data, 2023, 17(6): 1-21.

一、摘要

研究背景：社區(qū)檢測是網(wǎng)絡分析中的一個重要話題。近年來，在非負矩陣分解（NMF）技術的基礎上，發(fā)展了許多社區(qū)檢測方法。大多數(shù)基于NMF的社區(qū)發(fā)現(xiàn)方法只利用鄰接矩陣中的一階鄰近信息，存在一定的局限性。此外，許多基于NMF的社區(qū)檢測方法涉及稀疏正則化，以促進更清晰的社區(qū)成員。然而，在大多數(shù)正則化中，不同的節(jié)點被平等對待，這似乎是不合理的。

本文貢獻：針對上述局限性，本文在NMF框架下提出了一種基于節(jié)點中心度的社區(qū)發(fā)現(xiàn)方法。具體來說，我們設計了一種新的相似性度量，它考慮了高階鄰居的接近程度，形成了一種更具信息量的圖正則化機制，從而更好地細化檢測到的社區(qū)。此外，我們引入節(jié)點中心度和基尼不純度來分別衡量節(jié)點的重要性和社區(qū)成員的稀疏性。然后，我們提出了一種新的稀疏正則化機制，迫使具有較高節(jié)點中心性的節(jié)點具有較小的基尼雜質。

二、文章創(chuàng)新點

（1）我們提出了一種新的相似性度量，即h階加權Jaccard，并使用它作為一個重要的成分來正則化檢測到的社區(qū)。好的一面是，我們提出的h階加權Jaccard包含更多的信息，高階鄰居比現(xiàn)有的局部相似性措施，這是很好的社區(qū)檢測。

（2）我們利用節(jié)點中心性和基尼不純性形成一種社區(qū)正則化機制，使得中心性較高的節(jié)點的社區(qū)成員關系變得稀疏。通過降低具有低節(jié)點中心性的節(jié)點的重要性并增加具有高節(jié)點中心性的節(jié)點的重要性，可以更有效地進行針對社區(qū)檢測的非負矩陣分解過程。

（3）我們提出了一種新的NCNMF社區(qū)檢測方法，它利用新提出的相似性度量和稀疏正則化機制下的NMF框架。

（4）我們推導出一個有效的優(yōu)化算法的基礎上，理論上保證收斂的梯度下降法求解NCNMF。此外，整個社區(qū)檢測過程的計算復雜度進行了分析。它的規(guī)模與網(wǎng)絡中的節(jié)點數(shù)，這是相同的許多現(xiàn)有的NMF為基礎的算法，從而保證其效率的立方。

（5）我們在8個真實世界的基準網(wǎng)絡上進行了廣泛的實驗，以測試NCNMF，并與13種最先進的社區(qū)檢測方法進行比較。實驗結果不僅表明了NCNMF的巨大優(yōu)越性，而且表明NCNMF在有效性和效率之間取得了很好的平衡。此外，我們驗證了理論分析，并進行敏感性分析。

三、本文模型

1.準備工作

介紹本文中使用的主要符號和術語。然后，我們提出了幾個現(xiàn)有的相似性度量，the symmetric NMF model, and the homophily-preserving NMF model。

1、符號（Notations）

2、相似度量（Similarity Measures）

分為局部相似性和全局相似性。（local similarity measures and global similarity measures.）

局部相似性：樸素相似性測度[44]（the naive similarity measure）、共同鄰居測度[27]（the?Common Neighbor measure）、余弦測度[49]（the Cosine measure ）和Jaccard測度[49]（the Jaccard measure），等等。

由于余弦度量基本上用于計算文檔相似度。由于Jaccard測度是Common Neighbor測度的增強版本，研究人員現(xiàn)在基本上使用Jaccard測度而不是Common Neighbor測度來計算節(jié)點相似性。接下來，我們只關注樸素相似性度量和Jaccard相似性度量。

（1）the naive similarity measure：等價于鄰接矩陣。即，節(jié)點與節(jié)點有邊時值為1，否則值為0。定義如下：

（2）the Jaccard measure。利用相鄰節(jié)點集來計算相似度。它被定義為交集的大小除以兩個節(jié)點的鄰居集Γ（vi）和Γ（vj）的并集的大小。定義如下：

局部相似性度量有兩個主要優(yōu)點。一個是它們提供了一種直觀的方法來表征節(jié)點相似性。二是計算方便，耗時少。然而，局部相似性度量的缺點也是顯而易見的。它們只考慮了直接連接的鄰居對相似性計算的影響，忽略了許多有用的信息，例如節(jié)點的高階鄰居[42]。

全局相似性：全局相似性度量包括著名的Katz指數(shù)[17]、LHN-II指數(shù)[1]等。

Katz指數(shù)是通過在圖中搜索路徑并將由用戶指定的權重加權的每個路徑長度的計數(shù)相加來計算的，這是一種基于圖的計算方法，并計算全局網(wǎng)絡中節(jié)點之間的相似性。

LHN-II指標是基于正則等價性[1]提出的，當節(jié)點x的鄰居與節(jié)點y相似時，表明節(jié)點x和y相似，即節(jié)點的相似性是傳遞的。此外，子空間聚類模型[40]中構造的相似性矩陣也屬于全局相似性度量。在這些模型中構建相似性矩陣的最常用方法是全連接方法，其中所有點的權重值都大于0?？梢赃x擇不同的核函數(shù)來定義邊緣權重，最常用的是高斯核函數(shù)。它們可以通過考慮整個網(wǎng)絡拓撲來克服局部相似性度量的缺點，但它們的時間復雜度高于局部相似性度量，而局部相似性度量在大型網(wǎng)絡上不可擴展[42]。

3、Symmetric NMF

對稱NMF試圖通過兩個相同的因子矩陣來重建鄰接矩陣A，表示節(jié)點社區(qū)成員關系，它可以作為我們提出的NCNMF方法的構建塊。

模型定義：

其中，將社區(qū)成員矩陣表示為，其中每個元素反映的趨勢，SymmNMF將vi和vj之間的期望邊數(shù)建模為：很明顯，對于任何（vi，vj）∈E，a_aij應該與aij一致（使得邊緣建模是精確的）

4、homophily preserving NMFmodel (HPNMF)

我們引入了保同態(tài)NMF模型（HPNMF）[44]。HPNMF的基本思想是考慮節(jié)點的相似性。兩個節(jié)點越相似，它們的社區(qū)成員關系就應該越相似。根據(jù)[44]，給定一個定義良好的相似矩陣S ∈ Rn×n，實現(xiàn)上述思想的一個好方法是優(yōu)化以下優(yōu)化問題：

其中λ是控制節(jié)點相似性信息的重要性的正參數(shù)，γ也是控制H上的稀疏正則化的正參數(shù)，正則化器實際上是對H的l1-范數(shù)正則化以使它們更稀疏，并且L是定義為

其中，S是上述相似度矩陣，S'是對角矩陣，其中。

2.模型框架

在本節(jié)中，我們首先提出了一種新的相似性度量，即h階加權Jaccard，它利用了網(wǎng)絡中h階鄰域的結構信息。然后，我們開發(fā)了一種新的稀疏正則化機制的基礎上的節(jié)點中心性和基尼雜質。結合這兩種技術，我們提出了我們的NCNMF模型的社區(qū)檢測問題。

1、h階加權Jaccard相似公式

設h為表示跳數(shù)的非負常數(shù)，p為[1，h]范圍內的整數(shù)。對于一個給定的節(jié)點i，我們將其直接連接的鄰居記為Γ（vi），將其高階鄰居記為Γp（vi）= {vj ∈V:vj位于vi的p跳鄰域中且2 ≤ p ≤ h}。基于這兩個鄰域集，我們提出了一種新的計算節(jié)點相似度的方法，即h階加權Jaccard（記為w-Jaccard）相似度。其具體計算如下

其中是子相似度的權重在我們的方案中，隨p或q的增大而減小。這里的參數(shù)h建議在{1，2，3} [42]中設置為常數(shù)，表示節(jié)點vi最多可以取h階鄰居。

如第3.2節(jié)所述，等式（1）中的正常Jaccard相似性僅利用直接連接的鄰居的信息。這忽略了一些有用的信息，如節(jié)點的高階鄰居，導致節(jié)點相似性的準確性有限。我們使用下面的例子來具體說明w-Jaccard相似性相對于Jaccard相似性的改進。

例1.考慮圖2（a）和圖2（B），超圖G在G上添加了兩個新節(jié)點{v8，v9}和三條新邊{（v3，v8），（v4，v9），（v8，v9）}。讓我們關注兩個網(wǎng)絡中的社區(qū)c3。直覺上，圖2（b）中G中節(jié)點v3和v4之間的關系應該比圖2（a）中G中的關系更接近。當我們應用w-Jaccard相似性（即，方程（3）），在兩個節(jié)點上h = 2，Ωp，q =（5/8）pq [42]，我們得到圖2（a）中的Simw-Jaccard（v3，v4）= 73/128，圖2（B）中的Simw-Jaccard（v3，v4）= 361/605，這與實際相符。然而，如果我們應用正常的Jaccard相似性（即，方程（1）），我們發(fā)現(xiàn)SimJaccard（v3，v4）= 3/5在圖2（a）和SimJaccard（v3，v4）= 3/7在圖2（B），這與現(xiàn)實相矛盾。

思考：假設h=2時，節(jié)點vi和節(jié)點vj的sim計算為：節(jié)點vi的一階鄰居和節(jié)點vj的一階鄰居、節(jié)點vi的一階鄰居和節(jié)點vj的二階鄰居、節(jié)點vi的二階鄰居和節(jié)點vi的一階鄰居，以及節(jié)點vi的二階鄰居與節(jié)點vj的二階鄰居的加權之和。

2、基于節(jié)點中心性的稀疏正則化

在社交網(wǎng)絡中，社區(qū)的核心節(jié)點通常具有較高的度和較大的節(jié)點中心度。節(jié)點中心性度量節(jié)點的中心屬性，反映了節(jié)點在網(wǎng)絡中的重要性。通常，節(jié)點vi的中心性越大，它與鄰居節(jié)點形成社區(qū)的可能性就越大。受這一現(xiàn)象的啟發(fā)，我們在這一部分提出了一種新的基于節(jié)點中心性的稀疏正則化方案，即，強制具有更高節(jié)點中心性的節(jié)點的社區(qū)成員關系更稀疏。

（1）計算度矩陣

把每個節(jié)點的度表示節(jié)點的中心性。其中dii表示節(jié)點i的度

（2）計算基尼不純度

基尼不純度的介紹：[翻譯轉載] 基尼雜質(Gini Impurity)的簡單介紹-CSDN博客

基尼不純度就是在決策樹中用于量化聚類劃分的好壞程度

Gini Impurity 就是將來自數(shù)據(jù)集合中的某種隨機結果應用到數(shù)據(jù)集合中的隨機數(shù)據(jù)所得到預期誤差率。它的計算公式是：

C是數(shù)據(jù)類型的種類，p(i)是隨機一個數(shù)據(jù)是類型i的概率。

當訓練一個決策樹時，選擇最佳劃分方案的依據(jù)就是：Gini Gain 越高越好。
Gini Gain = 原Gini Impurity - 劃分后Gini Impurity
劃分后Gini Impurity = sum(各個分區(qū)所占權重 * 分區(qū)Gini Impurity)

在基于NMF的社區(qū)檢測的背景下，我們提出了以下公式來評估vi的社區(qū)成員是否是混沌的。

其中H =（hij）∈ Rn×k +是H1k = 1n的社區(qū)成員矩陣。

我們稀疏正則化方案的重點是降低具有較大節(jié)點中心性的vi的Gini（vi）值，從而使其社區(qū)成員更稀疏并增加其可分性。具體地說，我們的模型中所涉及的稀疏正則化項公式化

3.基于節(jié)點中心性的非負矩陣分解

基于上述討論，提出了一種基于節(jié)點中心性的變型NMF模型，即，NCNMF，提出檢測不相交社區(qū)。圖3顯示了我們提出的NCNMF方法如何檢測社區(qū)的流程圖。首先，根據(jù)輸入數(shù)據(jù)構造鄰接矩陣，然后從鄰接矩陣中獲得相似度矩陣和度矩陣。隨后，我們利用NCNMF模型獲得社區(qū)成員矩陣，從而劃分社區(qū)。相應的優(yōu)化模型被公式化為

(1):SymmNMF的目標函數(shù)，它是我們提出的社區(qū)檢測方法NCNMF的骨干。

(2):旨在將兩個相似的節(jié)點分配給同一個社區(qū)。這里，λ是控制節(jié)點相似性信息重要性的正參數(shù)，L是由等式（2）定義的圖拉普拉斯矩陣（其中S被我們的wJaccard相似性矩陣代替）。

(3):回想一下，[H（Ek×n ? HT）]ii表示節(jié)點vi的社區(qū)成員資格的基尼不純，因此項Tr[H（Ek×n ? HT）D]旨在降低具有更高節(jié)點中心性的所有vi的基尼（vi）。以這種方式，具有較高節(jié)點中心性的節(jié)點將被迫擁有更純的（即，稀疏）社區(qū)成員。這一項起著稀疏正則化的作用。在這里，α是控制該正則化的重要性的正參數(shù)。

四、實驗

1、實驗設置

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

我們使用了8個真實網(wǎng)絡的數(shù)據(jù)集，如表2所示。在每個網(wǎng)絡數(shù)據(jù)集中，社區(qū)由同一機構隸屬關系內的節(jié)點形成。作為預處理步驟，我們從網(wǎng)絡中刪除所有孤立的節(jié)點。得克薩斯州、康奈爾州、華盛頓州和威斯康星州的網(wǎng)絡從LINQS下載。2 Gene、Citeseer、Reality-call和BZR網(wǎng)絡從Network Repository下載。

1 https://github.com/wowoHead/NCNMF.
2 https://linqs.soe.ucsc.edu/data.
3 https://networkrepository.com/index.php.

（2）比較方法

我們將我們的算法NCNMF與十三種最先進的社區(qū)檢測方法進行比較，包括PNMF [48]，LPA [33]，GNMF [6]，SymmNMF [18]，DeepWalk [30]，ONMF [31]，MNMF [41]，Ego-Splitting [12]，NNSED [38]，DANMF [45]，HPNMF [44]，EdMot [21]和AGC [50]。

（3）參數(shù)設置

默認情況下，我們將所有基于NMF的方法的最大迭代次數(shù)設置為500。對于每種方法，我們運行20次，并報告平均值和標準差。對于我們的方法NCNMF，我們在{10?3，10?2，10?1，1，10，102，103}的范圍內調整λ和α，設置停止準則為（Jt?1 ? Jt）/Jt?1 ≤ 10?4，其中Jt表示第t次迭代的目標函數(shù)值，并設置參數(shù)δ = 105，h = 3，Ωp，q =（|V|/|E|）pq [42]，β = 0.5[11]。PNMF、LPA、SymmNMF、DeepWalk、ONMF、MNMF、EgoSplitting、NNSED、EdMot和AGC是無參數(shù)方法，其中不需要參數(shù)設置。對于GNMF，我們設置λ = 100 [6]。對于HPNMF，我們設置λ = 1和γ = 10?2 [44]，對于DANMF，我們設置層大小為n → 256 → 128 → k，預訓練迭代的最大次數(shù)為100 [45]。本實驗旨在評估所發(fā)現(xiàn)的社區(qū)w.r.t.地面真相社區(qū)。因此，對于所有競爭性方法，我們將檢測到的社區(qū)數(shù)量設置為地面真實社區(qū)的數(shù)量，如表2所示。

（4）評價指標

F-score

準確率

2.社區(qū)檢測方法的質量評價

本實驗評估了所有社區(qū)檢測方法的有效性。表3和表4列出了NCNMF和其他最先進的比較方法在所有8個網(wǎng)絡數(shù)據(jù)集上的F-Score和準確率性能(NCNMF的參數(shù)在6.1節(jié)介紹的范圍內調整，并報告了在最優(yōu)參數(shù)下的結果)，我們觀察到NCNMF在3/8和6/8的情況下表現(xiàn)最好，與13種最先進的社區(qū)檢測方法相比，NCNMF的離分和準確率最高。雖然NCNMF在德克薩斯、康奈爾、華盛頓和Citeseer網(wǎng)絡的F-Score方面不是最好的，但它達到了第二好的性能，并且性能幾乎與最好的方法一樣好。此外，NCNMF在F-Score和準確性方面均位居前2/8。這一出色的表現(xiàn)有力地證明了NCNMF的有效性。

3.相似性度量比較

在這個實驗中，我們測試了三種相似性度量的有效性，包括Naive相似性，Jaccard相似性和我們的w-Jaccard相似性（分別當h = 2和h = 3時）。具體來說，我們在所有網(wǎng)絡上運行不同版本的NCNMF，其中λ = 102，α = 1。F-score結果如圖4所示。我們發(fā)現(xiàn)，在所有的數(shù)據(jù)集上，無論h的值是2還是3，w-Jaccard相似性的效果都優(yōu)于樸素相似性和Jaccard相似性。特別地，在Reality-call網(wǎng)絡上對應于w-Jaccard相似性（h = 3）的F-得分值為0.9809，這遠大于naive和Jaccard相似性度量的F-得分值，其分別為0.6209和0.6235。從這個實驗中，我們可以得出結論，我們的新的相似性度量在所有數(shù)據(jù)集上都有絕對大的優(yōu)勢。此外，我們發(fā)現(xiàn)在小數(shù)據(jù)集上（即，Texas，Cornell，華盛頓，和Wisconsin網(wǎng)絡），w-Jaccard相似性在h = 2和h = 3時均獲得相似的性能。這是因為在小數(shù)據(jù)集上，可能沒有足夠的高階鄰居。但是在更大的數(shù)據(jù)集上（即，Citeseer和Reality-call網(wǎng)絡），h = 3的w-Jaccard相似度比h = 2的w-Jaccard相似度表現(xiàn)出更好的性能，這驗證了h = 3的w-Jaccard相似度在大規(guī)模網(wǎng)絡上可以獲得更多有用的信息。

4.消融實驗

在這一部分中，我們提出了一個消融研究，以顯示NCNMF的每個成分的有效性。具體地說，我們在不同的參數(shù)設置下運行了幾個NCNMF的消融版本，如下所述：

(1)設置λ=0和α=0，這顯示了構建塊A?HHT2F的性能。

(2)設置λ=10和α=0，這顯示了4.1節(jié)中提出的新相似性度量的性能。

(3)設置λ=0和α=10，這表明了第4.2節(jié)中提出的稀疏正則化的性能。

(4)設置λ=10和α=10，體現(xiàn)了新的相似性度量和稀疏正則化的融合性能。

我們報告了德克薩斯州、康奈爾、華盛頓州和威斯康星州網(wǎng)絡上所有不同NCNMF方法的F-Score結果。圖5顯示了新的相似性度量和稀疏正則化的結合可以產生更好的效果。

總結

在這篇文章中，我們提出了一種新的社區(qū)檢測方法，NCNMF。與現(xiàn)有的基于NMF的社區(qū)檢測方法不同，NCNMF不僅利用h階加權Jaccard相似度來提取更豐富的結構信息，而且引入節(jié)點中心度和Gini不純度來規(guī)范節(jié)點社區(qū)成員關系.為了優(yōu)化NCNMF，我們推導出了一個有效的算法，理論上可以保證收斂。我們已經(jīng)進行了廣泛的實驗，以評估我們的NCNMF方法在八個真實世界的基準網(wǎng)絡，實驗結果表明，NCNMF優(yōu)于國家的最先進的顯著。在未來的工作中，我們計劃研究如何將NCNMF擴展到有向網(wǎng)絡并檢測重疊社區(qū)。文章來源地址http://www.zghlxwxcb.cn/news/detail-810989.html

到了這里，關于Nonnegative Matrix Factorization Based on Node Centrality for Community Detection 論文筆記的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！