基于邻接点求解最大团问题

由于最大团问题(maximum clique problem, MCP)的复杂性、挑战性,以及在数据挖掘等各个领域的广泛应用,使得在计算机科学领域求解MCP问题具有非常重要的意义。本文通过介绍最大团问题以及研究意义,描述了最大团问题的研究现状,指出目前精确性算法和启发式算法解决最大团问题存在的不足,根据最大团中两两节点间均有边相连的性质提出了基于邻接点求解最大团算法,并论证该算法的正确性和完整性,最后将此算法应用于包含任意节点求其最大团的问题。

一种相对重要节点挖掘方法及其在犯罪网络中的应用

网络科学中相对重要节点的挖掘具有重要的应用价值,例如,通过已知犯罪分子查找其他犯罪分子。为此,文中提出了一种基于带重启随机游走的相对重要节点挖掘方法,并结合犯罪网络的两个特征来把该方法应用于犯罪网络的挖掘:根据犯罪分子会隐藏自己的特点对随机游走的初值进行设计;根据犯罪分子之间的通信人物很有可能就是罪犯的特点对随机游走的概率转移矩阵进行改进。最后将提出的方法同4个经典的相对重要节点挖掘指标进行对比,同时通过实际的犯罪网络来进行实验和分析,结果表明,文中的算法比经典的方法更能准确预测出犯罪分子。

基于聚类系数和节点中心性的链路预测算法

目前复杂网络领域受到越来越多人的广泛关注。其中链路预测是复杂网络研究中的一个热门的分支,被作为预测缺失链路和识别虚假链路的有效手段。传统基于相似性的复杂网络链路预测主要考虑每个节点的某个相似性指标,而该文提出一种基于聚类系数和节点中心性(CCNC)的链路预测算法,将度、聚类系数和节点中心性3个相似度指标结合,引入到复杂网络链路预测中。该算法使用度和聚类系数作为局部信息的指标,使用节点中心性表征节点在网络中的重要程度。最后,以6个真实网络为例,通过对比曲线下面积(AUC)和精确度(Precision),验证了CCNC算法的可行性和有效性。