基于正則無回路矩陣的網絡社團數目估計

王 林，趙月娥

(西安理工大學 自動化與信息工程學院，陜西 西安 710048)

基于正則無回路矩陣的網絡社團數目估計

王 林，趙月娥

(西安理工大學 自動化與信息工程學院，陜西 西安 710048)

針對社團檢測中社團數目未知的問題，提出一種基于正則無回路矩陣的社團數目估計方法。該方法通過定義一種正則無回路矩陣并利用其譜特性對網絡中社團數目進行估計。該方法計算高效，并且能夠適用于隨機塊模型和度糾正隨機塊模型。利用兩種人工網絡進行驗證，實驗結果表明，相比基于無回路矩陣的估計方法，該方法重點消除了度異質分布對社團數目估計的影響，從而提高了估計結果的準確率。

隨機塊模型；度糾正隨機塊模型；正則無回路矩陣；社團數目

0 引言

復雜網絡廣泛存在于自然界和人類社會，如地震網、萬維網、朋友關系網和科學家合作網等[1]。大量研究表明，許多真實的復雜網絡中都呈現出社團結構特性，那么對社團檢測是了解整個網絡結構和功能的重要途徑。

目前已有諸多社團檢測方法[2-4]，其中大多數方法依賴于網絡社團數目這一先驗知識，然而社團數目在實際網絡中通常是未知的，這極大地限制了這些方法的應用。鑒于此，許多學者致力于研究如何預先估計網絡中的社團數目。Saldana等人[5]提出了一種基于似然的方法，但是對大規模網絡而言該方法收斂速度慢且計算復雜度高；Chauhan等人[6]提出了一種基于鄰接矩陣主特征值分布的方法，對于相對稀疏的網絡而言，該方法收斂速度慢、計算成本高且只適用于隨機塊模型；……