现实生活中的很多真实系统都可以看作是复杂网络的一种拓扑抽象,如科学家合作网、生物动态分子网络、通信网络等。研究表明,社区结构可以说是复杂网络最重要的特征属性之一,即在同一个社区内部之内的节点互相之间紧密结合,不同社区间的节点连接则较为稀疏。社区发现的目的就是要挖掘并且分析网络中的社区结构用于预测实体行为和活动。目前,社区发现已经成为复杂网络中不可或缺的一项研究课题,不仅具有较高的理论价值,也具备广阔的应用前景。现阶段的社区发现算法可以分为静态社区发现算法和动态社区发现算法两大类。静态社区发现算法中又可以划分为基于图划分、基于模块度优化的方法等等。其中不乏有许多优秀的算法能够有效地识别出社区结构。然而,静态社区发现算法由于忽略了网络的动态时效性,使其难以适应真实网络中节点和边频繁变动的情况。因此,动态社区发现算法的研究逐渐受到人们的关注。动态社交网络可以看作由多个连续时间片的静态社区网络组成。常见的动态社区发现算法的目标是对每个时间片.形成快照检测,然后分析相邻时刻社区间的关系。这种设计思想往往会造成相邻时间片的社区划分结果偏差较大,算法运行时间效率低,适应大规模社交网络的可扩展性不足等问题。基于网络增量的动态社区发现算法由于在聚类时参照了前一时刻的信息,避免了对整个网络重新进行聚类,因此能有效降低算法的时间复杂度。本文在分析传统社区发现算法的基础上,针对现有算法的不足,提出了一种基于密度的增量动态社区发现算法,主要研究成果如下:(1)提出一种基于边密度的社区发现算法,将其用于动态社区发现初始时刻的聚类。首先,以边为单位对网络进行划分成若干子集,识别并过滤掉孤立边后,生成社区结构。然后,分离出边社区中的节点进行转化为节点社区,若两条边之间有公共交点,则将该节点视为重叠节点。最后,通过实验表明,该算法能有效提高社区发现质量,且能发现网络中社区间的重叠现象。(2)提出一种基于边密度和改进模块度的增量动态社区发现算法,首先,利用边密度算法对初始网络进行聚类。同时,改进现有社区节点归属判定方法,考虑相邻时刻增量对邻居节点社区归属改变的影响,避免了人工设定参数较复杂和不确定等缺点。然后,采用改进的模块度作为社区评价指标,在对社区的结构进行调整时综合考虑了历史时刻局部范围内节点的改变和当前增量变化量。最后,通过实验表明,该算法可以在时间复杂度近似于增量方法的前提下,取得较好的社区发现结果。