复杂网络研究涉及社交网络、学术网络、万维网、蛋白质作用网络等很多领域中的抽象网络。社区结构挖掘是研究复杂系统的关键工具。探索和发现网络社区结构对于了解复杂网络内在规律,开发其功能,预测其行为具有十分重要的意义和作用,特别是在大型复杂网络中进行社区划分,具有重要的实际意义。本文对社区划分算法进行了研究,主要工作和贡献包括以下几个方面:(1)针对局部社区划分算法中存在的初始节点依赖和候选节点判定难等问题,提出了一种基于节点传递相似性、现有的局部聚类性、广度优先遍历的两阶段局部社区划分算法(TSB)。该算法过程分为两个阶段,包括核心社区检测阶段和社区扩展阶段。算法开始时将初始节点拥有最大聚类度的邻居加入初始社区;综合节点相似度、遍历顺序提出了节点传递相似性度量,用来衡量核心社区候选邻居节点同初始节点、当前核心社区的连接紧密度;综合节点传递相似度、遍历深度和聚类度设置候选节点判定函数及动态阈值,使算法能自适应不同网络的不同部分。实验结果表明,TSB算法能有效地提高社区划分的准确率。(2)针对遗传进化算法中存在目标函数设定难和收敛慢的问题,提出了一种基于遗传进化的全局社区划分算法(TELGA)。该算法利用节点层边学习增大了重要的边在初始个体编码中的比例;两大类种群分别以强化社区内连接为主目标和以弱化社区间连接为主目标;划分层边学习根据种群精英个体的编码特性,通过调整边权重比例,影响种群变异过程来增大理想社区内部边在种群编码中出现的比例,减小理想社区间边在种群编码中出现的比例,提高算法找到解的速度。实验结果表明该算法的有效性和可用性。(3)针对非负矩阵分解算法中存在的特征矩阵维数大和添加节点问题,提出了一种基于增量非负矩阵分解的全局社区划分算法(CK-INMF)。算法改进了节点核心权重函数,并用其选出的社区核心节点来构造低维度的特征矩阵;利用增量非负矩阵分解,为新添加节点寻找所在的社区,避免大量的重复计算,实现动态添加节点;通过合并矩阵分解得到的初始社区,得到最终的社区划分结果。实验结果表明CK-INMF算法能够有效的提高算法的性能。