增量式動態社區發現方法

線上社會網路數據量大、動態性強，快速準確發現隱含社區結構並得到隱結構演化信息是實際套用的迫切需求。針對算法效率問題，許多增量式動態社區發現算法被提出，該方法的假設前提仍然是平滑性假設，認為動態社區演化過程中，大部分的拓撲結構保持相對穩定，僅有小部分結構會變化，所以，在識別前一時刻社區結構的基礎上，僅對改變的網路結構部分進行重計算，而其餘結構保持不變，以此提升計算效率。當前的增量策略主要分為基於物理學原理的增量策略和基於圖特徵的增量策略。

（1）基於物理學原理的增量策略將網路看成複雜物理世界．受牛頓萬有引力定律的啟發，Yang等人將網路節點間關係分為吸引力和排斥力兩種，通過疊代增量計算，使得所形成的社區內部吸引力越來越大，社區間的邊上的排斥力越來越大，最終連線邊斷裂，形成分割的社團結構。

（2）基於圖特徵的增量式動態社區發現方法一般首先利用靜態社區發現算法發現初始時間快照上的社區結構，然後辨識後續網路快照中結構變化的部分，對這小部分改變的結構進行計算，從而避免對全網路重新計算。主要的增量策略有基於圖分割特徵的、基於譜特徵的、基於矩陣分解等方法。