近年来,随着社交网络的兴起,图挖掘越来越受到研究人员的重视,有关图挖掘研究的论文在SigKDD、ICDM、SiamDM等会议中有逐年递增的趋势。极大团挖掘是图挖掘中的一个基本问题,有着丰富的研究意义与极高的实践价值。如进行社交网络分析、利用邮件网络推断社会等级、研究行为与认知网络的结构、对金融网络进行统计分析、对动态网络进行聚类、侦测各种恐怖活动和紧急事件等。本论文以极大团算法的研究为切入点,对这一基本的图挖掘问题进行了理论上的研究并给出了其实践中的应用。论文的研究主要分为三大部分:1.研究并实现了 Base BK算法、Improved BK系列算法和Kose系列算法,对部分算法进行对比实验,分析算法的适用场景与时空优劣。首先分析Base BK算法,这是最早的一个使用递归方式挖掘极大团的经典算法。进而研究Improved BK系列算法,这些算法致力于解决Base BK算法递归空间树规模过于庞大的问题,提出了各种启发式选择标志节点的方法对Base BK算法的递归空间树进行剪枝。其中著名的是最小计数器版本的Improved BK算法和随机CANDIDATES&NOT版本的Improved BK算法,论文都有理论分析与实现。也研究了 Kose系列算法,Kose算法使用迭代方式挖掘图中的极大团,虽然避免了生成不必要的子团,却导致内存消耗急剧增大。由此衍生了 Kose RAM算法和Kose Disk算法,它们分别将中间数据存入内存和硬盘,所以耗费的内存不同。本论文研究并实现了 Kose RAM算法。最后取七个经典的极大团挖掘算法,在单进程模式下实现,在相同的实验环境下做了 1000多个实验,根据实验结果反馈分析算法的原理并给出了不同环境下如何选择极大团挖掘算法的建议。2.研究FAMCELM算法,指出使其运行失效的场景,进而提出受限内存下的解决方案,并以理论和实验证明算法的可行性。Fast Algorithms for Maximal Clique Enumeration with Limited Memory 论文提出了在大规模图中挖掘极大团一个分布式的算法。这一算法有着三大优势:适用于内存有限的场景、减少了挖掘极大团的机器的CPU消耗、可以在并行环境下实现。研究中发现,面对图中存在度极大的节点的情形,论文中的SeqMCE算法会失效。分析了产生这个问题的原因,给出了解决这一问题的一个方案及严格的理论证明。在对SeqMCE做了其他的优化后提出了 Improved SeqMCE算法,这一算法解决了遇到度极大的节点的问题,代价则是重复挖掘了部分全局极大团。最后在内存受限的场景下运行Improved SeqMCE算法,从而证明其在实践中的可行性。3.依托于Improved BK算法和Improved SeqMCE算法,为解决统计段时间内不同的发送垃圾短信的手机号码总数的问题,提出了基于先验概率的Hash算法——GHash算法。作为算法的预处理部分,首先需挖掘出等长字符串(场景下则是手机号码)的统计规律。论文将字符串的各个位置抽象成一个图的节点,创造性地将挖掘统计规律的问题转化成寻找极长链的问题,进而转化成在其传递闭包中挖掘极大团的问题。在使用Improved BK算法挖掘出图中的极大团后,再将节点映射回原字符串的相应位置,从而得到原字符串的统计规律。为解决极大团挖掘算法为NP问题,算法耗时过久的问题,又提出了通过计算信息熵从而得到统计规律的一个子集的替代方案,这在手机号码的场景下运行良好。在一个有着3000多万手机号码的数据集上的实验表明,GHash算法所占用的内存远小于使用Bitmap算法所占用的内存;速度上则远快于使用AVL树、红黑树和Trie树完成检索的场景;相比较布隆过滤器,GHash算法是1000%准确的;相比较传统的部分Hash算法,如djb2、fnv-1、sdbm等,GHash算法无论是运行时间还是冲突数,都有明显的优势。