复杂网络中的边呈现不均匀分布,某些顶点构成的群组内部边较稠密,而群组之间的边较稀疏,网络的这一特性即社区结构。大量真实网络中包含互相重叠的社区,相比传统的社区,重叠社区更能揭示隐藏的规律。近年来,重叠社区发现已经成为主要挑战之一。重叠社区发现算法中一个新奇而有效的做法是划分边而不是顶点,这一方法即边划分方法。尽管边划分方法在重叠社区发现上有天然的优势,也受到了广泛关注,但该方法仍存在诸多不足。边划分方法中有边相连的两个顶点只能属于同一个社区,这导致发现的社区高度重叠。为了克服这一缺陷,本文提出了基于非对称加权图的边划分方法(Link Partition on Asymmetric Weighted Graph,LPAWG)。LPAWG首先把网络的每条边切分成两条非对称加权边。其次在将边社区翻译成顶点社区时,利用非对称加权边对顶点的偏向只保留偏向的顶点而忽略另一顶点。这一策略使有边相连的两个顶点可以属于不同社区,所以LPAWG可以发现合理程度的重叠社区。针对边划分方法中线图矩阵规模较大的问题,提出根据非重叠社区结构推断出某些边的社区归属从而削减加权线图规模的策略。将这一策略推广到LPAWG上提出加速的LPAWG(Accelerated LPAWG,ALPAWG)。在计算机生成数据集和真实网络上的实验结果表明,LPAWG的正确性明显优于边划分方法,同时ALPAWG在不降低正确性的前提下可以显著削减加权线图的规模。针对边划分方法中加权线图规模大难以求解的问题,提出基于对称非负矩阵分解的边划分方法(Symmetric Non-negative Matrix Factorization based Link Partition,SNMF-Link)。SNMF-Link基于的假设是数据可以通过边-顶点关联矩阵张成的子空间表达。这一假设可以显著减少未知矩阵的规模。提出用乘法更新法则(Multiplicative Update Rule,MUR)求解SNMF-Link,但MUR的优化方法收敛较慢。为了克服这一缺陷,进一步提出将增广拉格朗日方法(Augmented Lagrangian Method,ALM)应用在SNMF-Link上,并用最优梯度法求解。算法的复杂性分析表明SNMF-Link和ALM是有效性的。在测试数据集上的实验结果表明SNMF-Link在不降低正确性的前提下用时更少,ALM优化的SNMF-Link比MUR优化的SNMF-Link和典型的谱聚类方法Ncut(Normalized cut)用时都少。