摘要：随着社交网络规模的持续扩大,社交网络中社会关系的计算正逐渐成为数据挖掘研究的热点.如何高效获取社交网络中有价值的信息,如社交网络中适于投放广告的团体、客户关系中具有紧密关系的客户,具有重要的现实意义.对此,提出一个基于影响力的框架,来分析社交网络.首先,提出一种基于相似度的顶点间的权重度量.其次,通过顶点间的相似度来分配权重,改进PageRank算法计算每一个顶点潜在的影响力.最后,通过设置阈值,量化两点之间的影响力得分发现社交网络中的紧密子图.实验结果表明,基于影响力的紧密子图发现算法不仅在计算个人影响力和成员顶点间的共同影响力之间展现了很好的平衡,而且对于真实的社交网络也同样适用.

摘要：大规模图数据中的重要顶点与层级结构对于挖掘复杂网络(如社交网络、交通网络等)中有价值的信息具有重要意义.提出一种自顶向下的大规模时态图(k,h)-维护算法,对时态图中紧密度最高的前n层(k,h)-核,或满足自定义k,h值约束条件的核进行维护.首先提出识别(k,h)-最大层的方法 .当时态图中出现新的边时,为了定位当前时刻可能因新加入边导致核值需要更新的顶点的范围,提出候选插入子图与部分(k,h)-核的概念及相应的识别算法.针对加边情况,提出自顶向下的时态图(k,h)-核维护加边算法,根据部分(k,h)-核识别核值受加边影响的顶点并对其核值进行更新.针对当前时刻有已经存在的边被删除的情况,提出自顶向下的时态图(k,h)-核维护删边算法,对上一时刻的(k,h)-核做最小调整以得到当前时刻的核值.从理论上证明了算法的正确性,还在真实的时态图上设计了一系列对比实验.实验结果表明,在维护层数较少时下添加边,提出的核维护算法与其他对比算法相比,加速比可达几十倍;删边时,加速比也在1~2倍.提出的算法有良好的扩展性,对于增删不同数量的边和不同的(k,h)设置,都能保持较高的效率.

摘要：由蛋白质交互网络、社会网络及无线通信网络构成的图中存在许多不确定性。如何高效获取不确定图中有价值的信息,如蛋白质网络中关键的功能集团、社会网络中适于投放广告的团体及通信网络中应重点维护的区域等,具有重要的现实意义。从理论上证明了在不确定图中发现最紧密子图问题具有NP-Hard复杂性;基于树搜索策略提出了通过枚举解空间及剪枝获得最优解的算法TreeClose;针对树搜索算法TreeClose在处理大图时空间复杂度过高的问题,提出了基于贪心思想的2-近似算法GreedyClose。实验结果表明,通过上述算法可以高效快速地在不确定图中发现紧密子图,从而解决在实际应用中遇到的各种问题。

摘要：k核查询是一种社团查询,由于其可以在线性时间内被有效计算,因此在社团检测中具有较广泛的应用。图中边的权值在很多场景下具有较强的语义关系,但现有研究较少考虑图中边的权值。为提升k核查询的效率,在k核的基础上定义加权图中的紧密k核子图查询(CRKSQ)问题,并使用归约方法证明该问题是NP-难的。基于贪婪策略设计启发式算法CRK-G,通过迭代删除节点为CRKSQ问题找到一个近似解。在此基础上,从降低图规模和减少迭代次数两方面研究CRK-G算法的优化策略,分别提出使用图压缩策略的算法CRK-C及使用单次多节点删除策略的算法CRK-F。在Bio-GRID、Email-Enron、DBLP 3个数据集上的实验结果表明,相对于CRK-G算法,CRK-C、CRK-F算法在查询速度上有较大的提升,且平均误差均在8%以内。