一種結合節點信息和網絡結構的社區發現方法與流程
2023-11-30 17:17:36
本發明涉及一種結合節點信息和網絡結構的社區發現方法，屬於網絡分析與挖掘領域。
背景技術：
針對網絡的分析已成為最重要的交叉型研究領域之一，當前網絡研究中的一個熱點圍繞社區結構展開。社區這一概念的原始定義是有相同特點或者興趣愛好的一類人組成的團體。當開始將網絡結構作為反映真實世界複雜系統的模型，社區的概念已經不僅僅局限於人類關係，逐步擴展到了各種各樣的網絡中。社區發現的任務就是識別檢測出網絡中由節點組成的一系列群體，這些群體內部節點之間聯繫緊密，而群體之間的節點連接則相對稀疏，而這些群體我們稱之為社區。
網絡分為無權網絡和有權網絡兩種。無權網絡中節點和節點之間的關係有「無關係」和「有關係」兩種狀態，而有權網絡的權值則代表了節點之間相互作用的強度，網絡蘊含的信息也更加豐富。現實社會中存在許多無權網絡和有權網絡的實例，相應地也誕生了許多處理無權網絡和有權網絡的社區發現算法。
對網絡結構進行社區發現具有重要的意義，它不僅能直觀地表現出不同種類的網絡中模塊化的分組結構，還可以幫助人們認識網絡所代表的社會現象和系統、理解網絡的功能和作用、發現網絡中隱藏的信息和規律、預測網絡的行為和變化以及指導人們解決網絡所代表的現實問題等。
目前，社區發現主要分為兩大類。一類方法是基於節點信息，通過計算節點之間的相似度，利用聚類算法完成社區劃分。另一類方法是基於網絡結構，通過網絡節點之間的連接關係，利用社區發現算法完成社區劃分。雖然針對這兩種情況已經誕生了許多社區發現算法，但是這兩種方法均具有局限性，它們往往只注重一方面的節點信息而忽略另一方面的重要性。第一類方法得到的社區成員之間一般會具有相似的特徵信息然而相互之間連接不緊密，而第二類方法得到的社區成員之間關係連接緊密，卻不具有較多的共同特徵。這正是因為這兩種方法不能合理地、完全地結合併利用網絡節點的有效信息，所以根據這兩種方法得到的社區發現結果並不理想。
技術實現要素：
針對現有技術的不足，本發明提供了一種結合節點信息和網絡結構的社區發現方法；
術語解釋
無向網絡、有向網絡：所謂網絡，是由一些基本的單元和它們之間的連接所組成。根據這些連接邊是否有確定的方向，我們可以將網絡分為有向網絡和無向網絡兩類。
網絡結構，由節點與節點之間的連接邊組成。在網絡結構中，節點一般代表用戶，而邊則代表用戶之間的相互關係。除此之外，一般情況下每個用戶都會有用來描述用戶屬性的信息，這些信息由許多特徵組成。我們一般用這些特徵組成的向量來描述用戶的屬性，稱為特徵向量。每個用戶都對應一個特徵向量，根據不同用戶的不同特徵設置特徵向量的值。假設學生小明是一個節點，小明具有籍貫、年齡、性別、成績等特徵。我們用0、1來表示這些特徵。例如根據籍貫是否為山東、年齡是否在18-23之間、性別是否為男、考試成績是否及格這些特徵，用0表示否，1表示是。那麼，小明的特徵向量可以表示為(1,1,0,1)。
本發明的技術方案為：
一種結合節點信息和網絡結構的社區發現方法，具體步驟包括：
(1)根據節點特徵對社區劃分的影響程度，對節點特徵進行分類；
(2)根據節點特徵對節點進行內容相似度計算；
(3)根據網絡結構，得到網絡的鄰接矩陣A；
(4)設定閾值，更新網絡權重，生成有權網絡；
(5)根據實際需要設置參數，選擇社區發現算法，對步驟(4)得到的有權網絡進行處理，得到最終社區劃分。
根據本發明優選的，所述步驟(1)，具體包括：
a、根據節點特徵對社區劃分的影響程度，人為地為節點特徵分類；設定將某一節點特徵分為n類特徵；
b、對社區劃分的影響程度比較大的節點的某類特徵，為該類特徵賦予較大的權值，對社區劃分影響程度比較小的節點的某類特徵，則為該類特徵賦予較小權值；
n類特徵的權值依次設為n1,n2,...,nn，n1+n2+...+nn＝1。
步驟(1)舉例說明如下：某在校大學生為節點，每個學生有性別、參加的社團、課程等節點特徵，若想要社區劃分結果傾向於將愛好相同的學生分在一起，則將參加的社團這一節點特徵賦予60％的權重，課程這一節點特徵賦予30％的權重，性別這一節點特徵賦予10％的權重；若劃分結果傾向於將同一班級的學生劃分在一起，則可以將課程這一節點特徵賦予70％的權重，參加的社團這一節點特徵賦予25％的權重，性別這一節點特徵賦予5％的權重。
根據本發明優選的，所述步驟(2)，具體包括：
c、採用餘弦相似度計算方法，分別計算節點的每一類特徵的局部相似度，計算公式如式(Ⅰ)所示：
式(Ⅰ)中，Sij指網絡中節點i和節點j的相似度，分別是指節點i、節點j的節點特徵組成的特徵向量；
d、對節點的每一類特徵的局部相似度加權求和，求出全局相似度，節點i、j的全局相似度計算公式如式(Ⅱ)所示：
Simij＝n1Sim1+n2Sim2+...+nnSimn (Ⅱ)
式(Ⅱ)中，Sim1，Sim2，...，Simn分別代表n類節點特徵的局部相似度；Simij是指節點i和節點j的總相似度，即全局相似度。
根據本發明優選的，所述步驟(3)，具體步驟包括：
對於無向網絡，若網絡中的任意兩個節點i,j之間有連接，則設置Aij＝Aji＝1,若無連接，則設置Aij＝0，通過這種方式，得到網絡連接的鄰接矩陣A，Aij、Aji分別是指矩陣A中第i行j列的元素和第j行i列的元素。
根據本發明優選的，所述步驟(4)，具體步驟包括：
e、對於無向網絡，網絡中的任意兩個節點i,j之間連接邊的權重Qij設置公式如式(Ⅲ)所示：
Qij＝kAij+(1-k)Simij (Ⅲ)
根據式(Ⅲ)，得到網絡中所有節點兩兩之間的權重；
k為常數，取值為(0,1)。通過設置不同的k值，調節節點特徵和網絡結構對社區劃分影響的貢獻度，k值越大則網絡結構在社區劃分中起主導作用越明顯，k值越小則節點特徵在社區劃分中起主導作用越明顯，在實際使用時，根據實際情況的具體需要，設定k值的大小。
f、根據權重Qij的取值範圍，設置閾值q，設置公式如式(Ⅳ)所示：
q＝Qijmin+p*(Qijmax-Qijmin) (Ⅳ)
式(Ⅳ)中，p為百分數，p的取值為(0,1)，Qijmax、Qijmin分別指Qij取值的最大值和最小值；
舉例說明如下：q＝Qijmin+15％*(Qijmax-Qijmin)代表將權重大於Qijmin+15％*(Qijmax-Qijmin)的邊保留，將權重低於總體水平的後15％部分邊刪除，從而達到簡化網絡結構的效果。
設置閾值q的意義是因為在Qij的值非常小的情況下在i,j之間建立連接邊不僅對提高社區發現精度沒有積極作用，而且還會增大網絡的複雜度，增加社區發現過程的處理時間，所以此處設定閾值，將較小的權值排除，去除噪聲的幹擾。
g、生成有權網絡，具體如下：
若Qij>q，則在節點i,j之間建立一條連接邊，並給這條邊賦予權重Qij，若Qijq，則在節點i,j之間建立一條連接邊，並給這條邊賦予權重Qij，若Qij<q,則捨棄權重權重Qij，且節點i,j之間不建立連接邊，根據此規則，對原始網絡進行重建，生成有權網絡。
(5)根據實際需要設置參數，選擇社區發現算法，對步驟(4)得到的有權網絡進行處理，得到最終社區劃分。
具體步驟包括：選擇社區發現算法，對該有權網絡進行處理，得到最終社區劃分。所述社區發現算法包括目前較為成熟的派系過濾算法、標籤傳播算法、GN算法等社區發現常用算法。
若實際操作中對時間要求比較嚴格，可以選擇時間複雜度相對低的算法如標籤傳播算法，若對時間複雜度要求不高卻對精度要求相對較高，那麼可以選擇GN算法等。有的需要發現重疊社區，有的需要發現非重疊社區。根據不同場景，靈活選擇合適的社區發現算法，完成社區發現過程。