高效正确地划分网络社区有助于探究网络的结构和功能,发现其中隐藏的规律及预测可能发生的行为,是进行网络分析的基础和关键,有着极为重要的理论意义和广泛的应用前景,这也是众多研究者们的关注重点。目前对于社区划分算法的研究已有较多成果,如GN算法、LPA算法、FastUnfolding算法等,但是这些研究成果在实际应用中仍存在一定的局限性和不足之处。例如:依赖于先验知识(如社区个数、每个社区内的节点数目等)的输入、社区划分结果不稳定、社区划分的质量偏低等。主要是因为大多数方法没有充分考虑节点的行为特性、利用节点之间的关系强度,或只注重算法的运行速率而忽视了社区结构的质量,容易造成社区结构质量低、效率低等问题。因此,充分考虑节点的行为特性、分析节点间的关系强度和节点行为导致的网络变化等特点,研究基于节点历史行为的网络社区划分算法,对提升社区划分算法的效率和准确性具有重要意义。本文根据网络结构的特点,将网络分为静态网络和动态网络,分别研究社区划分算法。在静态网络中,针对其他算法依赖于先验知识的输入、社区划分的结果不稳定、只能进行非重叠社区的划分、社区划分的质量低等缺点,在考虑节点间的关系强度及社区的模块度的基础上,提出基于最大化模块度的重叠社区划分算法。首先算法基于节点的历史行为,分析节点的运动规律,计算节点间的关系强度,得到一个加权无向网络图;其次,根据得到的网络图进行边排序并构建初始社区,节点的关系强度越大,表明两个节点的关系越稳固越容易形成一个社区,两个节点在社区中的位置也更靠近社区的中心;最后,对得到的初始社区进行扩展,基于模块度值的优化,不断地向初始社区中增加新的节点,直至达到终止条件。在动态网络中,考虑到在较短的时间内,小规模的网络变化不会使网络结构发生显著改变,仅有少数相关节点及其邻接点有可能发生隶属社区的变化,网络结构大体稳定,提出基于网络增量的动态社区划分算法。该算法首先将由节点行为导致的网络增量变化细分为增加和删除孤立节点、增加一条社区内部边、删除一条社区内部边、增加一条社区外部边、删除一条社区外部边、边的权值发生变化等六种原子操作;其次针对这六种原子操作分别给出详细的处理方式,分析对节点隶属社区及相邻节点的影响;最后综合分析节点行为引起的以上所有操作的结果集,从而降低了算法的复杂度,实现了网络社区实时高效地划分。本文通过仿真实验,将所提算法与经典同类算法作对比,证明了在不同的网络结构下两个社区划分算法的高效性。