网络是一种广泛应用于描述现实世界的既简单又直观的方式。若将现实世界的个体抽象为节点,个体之间的相互作用或关系抽象为节点之间的边,则现实世界中许多系统都可以抽象表示为网络。例如,人及人之间的社交关系可以表示为社交网络;蛋白质及蛋白质之间的相互作用可以表示为蛋白质交互网。
社区(又称簇、社团等)是由连接紧密的节点组成的网络子集,而社区之间的连接通常被认为是相对稀疏的(不过,新的研究表明,在某些网络中部分社区之间的重叠部分连接更紧密)。社区是网络中普遍存在的一种重要的中观结构,因此,对社区进行研究具有重要的意义。
对网络中社区的研究最早可以追溯到1955年。2002年,美国科学家M.格拉文(M.Girvan )和M.E.诺曼(M.E.Newman)首次提出运用图分割的思路对网络中存在的社区进行检测。之后,社区研究受到了计算机科学、网络科学、物理科学、社会科学等多个领域的研究学者的关注,并成为一个研究热点。不过,大多数研究都将网络看作是静止不变的,或是将网络在某个时刻的状态作为研究对象。然而现实世界的许多网络通常会随着时间的推移而发生变化,网络中的社区也会随之发生改变。因此,越来越多的学者开始关注和研究社区的动态变化,并用社区演化这一术语来指代社区的动态变化情况。
根据节点数的变化情况,社区的演化行为被归纳为7种演化事件,即:形成、持续、消失、扩展、收缩、合并、分裂。形成指由于节点间的关系变得紧密,聚集在一起产生了新的社区;持续指原有的社区保持不变;消失指原有的社区因网络结构的改变而不再存在;扩展指已有的社区接纳了新的节点,收缩则指某些节点离开了社区;合并指已有的两个或多个社区合成了一个更大的社区,分裂则指一个已有的社区分裂为两个或多个更小的社区。
除了上述7种社区演化事件外,研究学者也开始关注社区内部的关系紧密度的变化,从更细粒度的角度研究社区的动态变化情况。因此,社区演化还包括社区内部节点之间的关系变化。
对社区演化的研究主要包括社区演化追踪、社区演化预测等。社区演化追踪是对社区演化行为进行追踪,其首要任务是分别获得网络变化前和变化后的社区结构,然后通过匹配变化前后的社区以检测社区的演化行为;社区演化预测则是根据观察社区的历史演化行为,预测未来一段时间内社区将发生什么样的演化。
社区是网络中的一种重要中观结构,因此,社区演化可以帮助探知社区的变化情况,揭示网络的内在动向,对捕捉和掌握网络的发展趋势起着不可忽略的作用。网络是现实世界中各种复杂系统的一种有力描述方式,社区往往反映了网络中存在的某种模式或功能,因此,社区演化能指导对相应系统的行为模式或功能的研究,对相应系统的发展有重要的价值。例如,通过追踪和分析蛋白质交互网中的社区演化行为,有利于生物学中对蛋白质的功能研究;通过对社交网中的社区演化行为进行追踪,有助于人类学中对人的行为模式研究。
社区演化与网络变化息息相关,其研究涉及多个领域的技术。因此,社区演化的研究有助于推动网络科学、社会科学、计算机科学等诸多学科的发展。