基于核心節點逐層擴展的標簽傳播社區發現方法*

翟鎮新 於躍成 谷 雨 景道月

（江蘇科技大學計算機學院 鎮江 212003）

1 引言

隨著互聯網技術的發展和社會網絡規模的不斷擴大，人與人之間的交流形式發生了巨大變化，人們獲取的信息量也呈爆炸式增長。社會網絡具有信息大、無標識、社區結構等特性，其中社區結構是社會網絡的基本性質。所謂社區結構是指一個網絡可以分為若干個社區，社區內節點相似度較高且連接相對緊密，社區間節點相似度較低且相對稀疏。社區發現可用于社交平臺用戶群組的發現，以實現相關商業廣告的投放；通過社區發現并挖掘群組的最新討論話題，可以向用戶更好地推薦感興趣的話題。

為了能夠實現社區的有效劃分，基于隨機游走的方法［1］、基于模塊度優化的方法［2～3］以及基于圖分割的方法［4～5］被相繼提出。這些方法主要依據網絡結構進行劃分，當應用于數據規模較大的社會網絡時，便會面臨迭代周期較長，算法復雜度較高等一系列問題。

2007 年，KUMARA 等學者［6］首次在面對非常繁瑣的社會網絡時，嘗試將標簽傳播模型（Label Propagation Algorithm，LPA）運用其中做社區發現的研究。實驗結果表明，使用LPA模型的社區發現時間效率等方面指標都有了巨大的突破。該算法模型不需要提前知道真實的社區個數有多少，僅依賴于社會網絡的自身結構。LPA 算法復雜度較低，被廣泛應用于大規模社會網絡的社區發現。

然而，LPA 在每次的迭代過程中存在著隨機性，致使每次社區發現的結果都不一致。造成LPA算法穩定性較差和隨機性較高的主要原因在于該算法沒有充分考慮節點自身的影響力，網絡中所有節點均被平等看待。……