信息网络是信息安全等应用领域重要的研究对象，其中一个重要的研究内容是寻找社区结构。网络的社区结构是指整个网络可以分成多个节点集合(社区)，每个集合内的节点之间联系紧密，而与其它集合的节点联系稀疏。本文以实际应用中的超大规模信息网络(M网络)为背景，研究如何提高寻找社区结构的效率和质量。在效率方面，研究了层次凝聚聚类算法和基于密度的聚类方法。在质量方面，研究了针对微观结构的节点间联系量化方法，以及针对超大规模网络的量化方法。为了高效率地处理超大规模网络，还提出了预处理和划分算法。　　 本文的主要贡献是：　　 ●高质量的社区发现算法。该算法在微观结构上使用Jaccard相似性来量化节点间联系紧密的程度，并根据节点邻域内相似性的分布寻找联系最紧密的邻居，将联系最紧密的节点相连即得到基于相似性的社区。这些社区被基于模块性(Modularity)的算法合并得到最终的社区结构。在大量数据集上的实验结果表明，这个基于相似性的社区发现算法显著提高了社区结构的质量。　　 ●高效率的社区发现算法。本文研究了如何提高层次凝聚聚类算法的效率。从宏观角度出发，本文分析了类的合并对整个凝聚过程的影响，指出了层次凝聚聚类算法的效率取决于每次合并的两个类的邻居数和共享邻居数，整个凝聚过程则被准则函数控制，而在准则函数中考虑类的邻居数能够显著提高算法的效率。根据对凝聚过程和准则函数的分析，本文给出已有方法低效率和低质量的原因，并提出了三个新的准则函数。实验表明，它们的效率显著优于已有的准则函数。　　 ●超大规模网络上的社区发现算法。本文分析了已有方法在超大规模网络上的质量问题和效率问题。通过使用三角形分析节点间联系，给出了高效率寻找三角形的方法和M网络的三角形分布规律。通过定义三角形密度来量化节点间联系，进一步将密度局部极大的三角形相连即获得社区。本文提出了社区发现算法中如何使用少量内存和顺序访问磁盘的改进方法。在实际的M网络上应用上述改进方法找到了联系紧密程度差异巨大的社区，这些社区有的只包括一个三角形，有的平均每节点上三角形数超过9000个。　　 ●基于倒排表的图的预处理算法。本文提出Gring算法，以倒排表表示图，将所有节点放在同一维度上处理；通过分组操作将相同标识的节点聚集在一起，避免了对节点映射关系的访问；将分组操作并行化以提高处理效率。实验结果表明，Gring算法使用2GB内存处理了有74亿条边的M网络。　　 ●基于磁盘的超大规模网络划分方法。本文提出基于统治集的粗化算法处理图不能被内存容纳时的情况。该算法在迭代地顺序访问数据时仍然有效地引入随机性。该算法结合网络的结构特征，有效处理了孤独的统治者现象，并控制了复节点的规模。在M网络上的结果表明，基于统治集的方法每次将图的规模缩小近一个数量级，划分的负载不平衡性为1.03，割边不足总边数的5％。