[發明專利]一種基于相似性的社區檢測的方法

有效

• 申請號: 201810987366.0
• 申請日: 2018-08-28
• 公開（公告）號: CN109255433B
• 公開（公告）日: 2021-10-29
• 發明（設計）人: 楊旭華;沈敏
• 申請（專利權）人: 浙江工業大學
• 主分類號: G06K9/62
• 分類號: G06K9/62;G06N3/04;G06Q50/00
• 代理公司: 杭州斯可睿專利事務所有限公司 33241
• 代理人: 王利強

1.一種基于相似性的社區檢測的方法，其特征在于：所述方法包括如下步驟：

步驟一：構建一個具有N個節點的無向網絡模型G(V,E),V為節點，E為連邊；

步驟二：任意選取兩個節點i和j，計算兩個節點的共同鄰居集合Int(i,j)＝(Γ_i∩Γ_j)和聯合鄰居集合Uni(i,j)＝(Γ_i∪Γ_j),遍歷網絡中所有節點對，計算并記錄相應節點對的共同鄰居集合和聯合鄰居集合；

步驟三：在網絡中任取一個節點i，計算該節點的局部度數比

其中D(i)表示節點i的度數，一個節點的度數為該節點的相連鄰居節點的數量，Γ(i)表示與節點i相連的所有鄰居節點并包括節點i，遍歷網絡，計算并記錄網絡中所有節點的局部度數比；

步驟四：計算網絡中包含每個節點的PageRank值的向量

x＝D(D-αA)^-1，

其中，x就是所計算的包含網絡每個節點的PageRank值的向量(PR₁,PR₂,PR₃,…,PR_N)，上述向量計算公式多次迭代以后x會收斂到一個非常接近真實的中心性值的值，D是網絡對應的對角矩陣，其元素是D_ii＝max(k_i,1)，k_i是節點i的度；α是一個正的可調參數，A是網絡的鄰接矩陣，表示網絡節點之間連邊關系，A_ij＝1，表示節點i和j之間有連邊，反之則表示沒有連邊；

步驟五：在網絡中任意選取節點i,計算連邊(i,j)的度數比聚類值

該值表示節點i和j的度數比相似性，遍歷網絡，計算并記錄網絡中所有節點及其連邊的度數比聚類值；

步驟六：在網絡中任意選取節點i，找出與其度數比相似性最高的節點w,w為當連邊(i,j)的度數比聚類值取最大值max{sim_P(i,j)},j∈Γ(i)時的j，遍歷網絡，找出所有節點對應的度數比相似性最高的節點；

步驟七：在網絡中任意選取節點i,計算連邊(i,j)的PageRank中心性聚類值

該值表示節點i和j的PageRank相似性，遍歷網絡，計算并記錄網絡中所有節點及其連邊的PageRank中心性聚類值；

步驟八：在網絡中任意選取節點i，找出與其PageRank相似性最高的節點m,m為當連邊(i,j)的PageRank中心性聚類值取最大值max{sim_PR(i,j)}，j∈Γ(i)時的j，遍歷網絡，找出所有節點對應的PageRank相似性最高的節點；

步驟九：在網絡中任意選取一個節點i，將與其度數比相似性最高的節點j劃入到同一個社區,遍歷網絡，將所有節點與其度數比相似性最高的節點劃入同一社區，得到初始社區劃分；

步驟十：在網絡中任意選取一個節點i，找到與其PageRank相似性最高的點j，如果節點i和j不在同一個社區，合并這個節點所在的初始社區；遍歷網絡，將每個節點與其PageRank相似性最高的節點所在的社區合并，得到最終的社區結構。