線上社交網路社區發現算法是一系列能夠在線上社交網路發現社區的算法。
基本介紹
- 中文名：線上社交網路社區發現算法
- 外文名：online social network
線上社交網路]的社區發現算法的思想是基於社交網路結構的拓撲結構，將網路劃分成多個簇，簇內用戶緊密連線，簇間用戶連線稀疏。在計算機科學領域，該問題一般被稱作圖分割問題。Kernighan-Lin是一種基於貪婪最佳化策略的算法，該算法通過定義一個目標收益函式，通過貪婪搜尋的方式查找使得目標收益函式值最大的網路分割。譜平分法從網路的拉普拉斯矩陣出發，通過研究該矩陣的特徵值和特徵向量從而達到對網路拓撲結構進行二分的目的，疊代使用該方法可以獲取社區數目大於2的社區劃分。GN算法中，為了衡量網路社區結構劃分的好壞，他們基於複雜網路和隨機網路結構特徵的比較，提出了模組度的概念，GN算法本質上講是一種網路分裂算法，它通過自定義的邊介數指標來標識社區之間的網路連邊，通過疊代去除邊介數最大的連邊，從而將網路分裂為若干虛擬社區結構。針對某些需要細緻刻畫社區結構的套用，信息科學領域的專家也從資訊理論的角度出發，將網路拓撲結構映射為數據編碼問題，通過構造編碼長度最短的虛擬社區劃分從而達到社區發現的目的。該類算法以Infomap算法為代表，可以更高精度地發現網路社區，主要套用於需要精確分析社區結構的場合。針對網路拓撲結構中若干節點同時隸屬於多個社區的現象，Gergely Palla等在2005年提出了重疊社區概念，利用派系和團的定義去發現網路中的重疊社區和處於社區邊界位置的橋節點。通過研究真實網路拓撲結構特性和假設的網路模型之間的差異，借用貝葉斯推斷等數學工具，Mark Newman等人提出了基於機率模型的社區結構發現算法，通過最大化似然機率，實現重疊結構的社區的發現。以上算法更多地側重於社團結構的精確度方面，較少考慮算法的時間複雜度，時間複雜度一般相對較高。就社交網路而言，上述方法只能適合於規模較小的社交網路中的虛擬社區發現。在現實情況下，也常需要分析具有規模大、節點信息種類繁多等特點的社交網路中的虛擬社區，如此就希望社區發現算法不但要具有較高準確度也需要具有較低的計算時間複雜度。同時考慮該兩方面需求，學者們也從不同角度出發提出了一些新的社區發現算法，可適合於較準確較快速發現較大規模社交網路中的虛擬社區。從社區結構的局部結構特徵出發，人們提出了基於局部擴展的社區發現算法。該類算法往往從一個或者幾個網路核心節點出發，通過定義局部收益函式，採用貪婪策略將該節點周圍的節點吸收入已存在的虛擬社區結構中。由於該類算法只利用了網路局部拓撲結構，因此可以在尚未構建全網拓撲結構圖的情況下發現和分析用戶關注區域的社區結構。為了提高網路社區發現的效率，Usha Nandini Raghavan等人提出了一種基於標籤傳播的社區發現算法。該算法通過為每一個節點賦予唯一的標籤，並按照節點鄰居的多數標籤疊代更新其自身的標籤值，最終收斂到部分網路節點共享同一個標籤的穩定狀態，享有相同標籤值的節點即為屬於同一個社區的節點。該類算法可以在已知網路拓撲結構全貌的情況下，線上性時間內發現網路社區結構。
