基于標簽影響力的半同步社區發現算法

汪焱 黃發良 元昌安

摘 要：微博網絡與社交網絡等的交互式社會信息網絡規模的快速增長對社區發現提出巨大挑戰。標簽傳播算法（LPA）雖然在時間復雜度上具有很大的優勢，但是其內在的多種隨機策略使得算法穩定性不高。針對LPA的隨機問題，提出了一種基于影響力的半同步標簽傳播算法（ISLPA），能有效地避免振蕩問題，巧妙地實現了相鄰節點之間的同步更新，并結合影響力從初始標簽、選擇鄰居節點和更新順序三方面進行了改進，摒棄了原有的隨機策略。真實網絡和人工網絡的實驗結果表明，ISLPA具有較高的穩定性與有效性，與其他LPA相關算法相比存在明顯的優勢。

關鍵詞：社區發現；標簽傳播法；半同步；節點影響力；振蕩

中圖分類號： TP393 文獻標志碼：A英文標題