[發明專利]考慮社區結構穩定度和增量相關節點進行社區發現的方法

有效

• 申請號: 201710829612.5
• 申請日: 2017-09-14
• 公開（公告）號: CN107609982B
• 公開（公告）日: 2020-11-24
• 發明（設計）人: 郭昆;郭文忠;陳羽中;牛玉貞;李國輝
• 申請（專利權）人: 福州大學
• 主分類號: G06Q50/00
• 分類號: G06Q50/00;G06K9/62
• 代理公司: 福州元創專利商標代理有限公司 35100
• 代理人: 蔡學俊

本發明涉及一種考慮社區結構穩定度和增量相關節點進行社區發現的方法，包括以下步驟：1、生成初始社區集，設置社區的初始權重，并初始化迭代時刻；2、計算增量相關節點集合IV_t；3、遍歷每個社區，解散社區集NS_t中社區權重和社區規模小于閾值的社區；4、對集合IV_t中的節點進行社區劃分，生成新社區；5、遍歷每個新社區，解散社區規模小于閾值的新社區；6、遍歷剩余相關節點集合IV_t?rm中各節點，計算節點與相鄰社區的相似度，將其加入相似度最高的社區，生成社區集NS_t；7、更新每個社區的穩定度和權重；8、計算NS_t的社區結構穩定度；9、判斷是否滿足迭代停止條件，以結束計算。該方法可以高效、準確地進行社區發現。

技術領域

本發明涉及社交網絡上的重疊社區發現技術領域，特別是一種考慮社區結構穩定度和增量相關節點進行社區發現的方法。

背景技術

隨著Web 2.0技術的發展，人們通過注冊Twitter、FaceBook、微博等社交平臺的帳號，相互認識并成為好友。因此，社交網絡已經成為人們生活中不可或缺的一部分。復雜網絡可以被抽象為有向或無向圖結構，借助圖論的相關工具與方法，可以刻畫社區結構，并設計基于圖論方法的社區發現算法。社區結構的發現就是將網絡節點按照其內在的拓撲結構連接的緊密程度劃分成若干個子圖的過程。分析并發現其結構對于用戶行為分析，情感分析，個體影響力分析等都具有重要作用。

針對復雜網絡的特征，如小世界、無標度、擁有社區結構等。有許多學者進行了大量研究，提出了很多經典的社區發現算法。傳統對社區結構的研究主要針對靜態網絡的社區發現，基于MapReduce等并行計算模型的靜態社區發現算法已經能夠很容易地處理包含大規模的社交網絡。但是，在真實環境中，網絡并不是一成不變的，它們往往隨著時間變化，具有動態的特征。目前，動態網絡的社區檢測主要包括進化聚類和增量聚類。增量方法將前一時刻社區檢測的輸出結果作為下一個時刻的輸入，由于增量聚類的時間開銷較少，因此，基于增量的社區劃分算法得到了廣泛關注。

現有的增量社區發現算法在社區發現方面已經取得一定成果，但仍然存在以下幾個問題：首先隨著時間的推移，基于增量式的社區發現會存在累積效應產生的誤差；其次，面對更大規模的社交網絡，如何提高算法的運行效率；最后，只考慮了所有社區的變化，而沒有考慮各個社區的變化情況。

發明內容

本發明的目的在于提供一種考慮社區結構穩定度和增量相關節點進行社區發現的方法，該方法可以高效、準確地進行社區發現。

為實現上述目的，本發明的技術方案是：一種考慮社區結構穩定度和增量相關節點進行社區發現的方法，包括以下步驟：

步驟1：采用SLPA算法在網絡G₁上生成初始社區集NS₁；

步驟2：對任意社區c∈NS₁，設置社區c的初始權重wc(c,t₀)＝1.0；

步驟3：初始化迭代時刻iter＝2；

步驟4：計算t時刻相較于t-1時刻的增量相關節點集合IV_t；