动态网络社区发现综述

高 阳， 张宏莉

( 哈尔滨工业大学 计算机科学与技术学院, 哈尔滨 150001)

0 引 言

真实世界网络的拓扑结构总是在不断变化的，网络随时可能会增加、删除节点或者边，网络的社区结构也会随之变化，于是就产生了动态网络的社区发现问题。动态网络可以采用2种模型来描述[1]：

(1)TN (Temporal Networks)[1-4]。 动态网络可表示为图G=(V,E,T), 其中V表示动态网络中节点的集合，V中每个元素(v,ts,te)(ts≤te)包含3个基本属性，v表示网络中一个节点，ts,te∈T分别表示该节点在网络中出现和消亡时间点；E表示动态网络中边的集合，E中每个元素(u,v,ts,te)(ts≤te)包含4个基本属性，u,v∈V表示该边的2个端点，ts,te∈T分别表示该边在网络中出现和消亡的时间点。

(2)SN (Network Snapshots)。 动态网络表示为一个向量〈G1,G2，…，Gt〉, 包含动态网络在每个时间点的拓扑结构，其中Gi=(Vi,Ei)，Vi,Ei分别表示该时间点对应的节点和边的集合。

1 动态网络社区发现概述

给定一个动态网络，一个动态社区DC (Dynamic Community)表示一些具有时间属性(period)节点的集合，DC={(v1,P1),(v2,P2)，…，(vn,Pn)}，其中Pi=((ts0,te0),(ts1,te1)，…，(tsN,teN))(tsj≤tej)表示节点vi的N个存在时期。动态网络社区发现是指发现动态网络中所有的动态社区[1]。动态网络的社区发现主要有2个研究目标，对此可做阐释分述如下。

(1)快速准确地发现动态网络在每个时间点的社区结构。

(2)建立演化链来描述社区的生命周期及演化过程[1]。

动态网络中的社区可以发生以下变化：

(1)出生。指一个社区第一次在网络中出现。

(2)消亡。指一个社区从网络中消失，该社区内全部节点不再隶属于该社区。

(3)变大。一个社区的规模由于加入了新节点而增长。

(4)收缩。一些节点移出某个社区，该社区规模因此变小。……