局部最大核子圖搜索算法研究

羅碧彤 孫晶 李源 李欣蔚

（北方工業大學信息學院 北京市 100144）

1 引言

由于圖形數據在不同應用中的普遍存在，圖形分析已經引起了研究界和行業界的廣泛關注。圖分析中的一個主要問題是給定一個圖，識別圖中的內聚子圖，如k核，k型桁架，派系，n-派系和n-族。其中，k核能在線性時間復雜度內計算，被定義為無向圖G的極大子圖，使子圖中的所有頂點的度至少為k。社區搜索在社會網絡分析中具有重要意義，對于圖中給定頂點，目標是找到該頂點所屬的最佳社區。直觀地說，對于給定頂點的最佳社區應該在頂點附近。Cui等人提出了一種局部搜索策略，即在一個頂點附近進行搜索，以尋找該頂點的最佳社區。大多數現實生活中的復雜網絡，包括互聯網、社交網絡和生物神經網絡，都包含了社區結構。網絡可以被劃分為組，其中連接緊密，組與組之間的連接是稀疏的。在真實的網絡中尋找社區是一項重要的分析任務，因為社區結構充滿意義，它們與網絡的功能高度相關。由于社區結構的重要性，社區搜索的問題，即尋找頂點最可能的社區，對許多現實生活網絡和應用十分重要。在信息時代，圖的規模變得巨大，圖模型所代表的數據中的價值也越來越重要。因此，在大規模圖中尋找核數最大的包含查詢點的極大連通子圖是一個重要且有意義的問題。在探索核數最大的包含查詢點的極大連通子圖的過程中，從查詢點開始向外擴展，其中判斷擴展的頂點是否具有提升當前k核的能力是擴展階段的主要問題。……