论文部分内容阅读
随着微博、论坛、即时通讯等社会网络应用系统的蓬勃发展和迅速普及,社会网络已成为人们生活中不可或缺的一部分,有关社会网络的分析与研究也成为了关注的热点。其中,发现整个网络的社区结构以及演化过程中的链接预测是十分关键的问题。通过对真实网络的结构特征和行为模式的研究,发现潜在的演化规律,并对网络行为进行预测,帮助解释社会现象,如网络信息传播激励、用户态势分析等。本文重点围绕加权网络的社区发现和链接预测两个问题展开研究,主要内容包括以下几个方面。首先,针对AGMA算法存在的问题进行改进,提出一种基于连接强度的加权网络社区发现算法CRMA。该算法分为聚类、再聚类、社区合并三个阶段。在前两个阶段,为解决AGMA算法对某些节点无法聚类或划分不合理问题,基于节点强度、连边符号等网络拓扑特征,定义了节点与社区的连接紧密度,并综合考虑节点与社区的朋友系数以及当前节点邻居节点的聚类情况,完成了所有节点的聚类,从而发现了初始社区。在第三阶段,为解决AGMA算法针对某些无权网络划分结果模块度较低的问题,定义了社区密度和社区间的连接强度。当两者满足一定关系时合并对应的两社区,以优化初始划分结果,从而得到了最终的社区结构。其次,针对现有加权相似性指标的不足之处,为实现加权网络更为合理准确的划分,提出一种基于共同邻居的加权网络社区发现算法IEM。该算法分为形成初始社区、扩展社区、合并社区三个阶段。在前两个阶段,重点考虑了两节点的公共邻居节点对于两者的相似性影响,定义了共邻节点作用系数以及共邻节点连接强度。针对没有公共邻居的情况,定义了边权强度作为两节点的相似度。在此基础上得到了两节点基于共邻节点的加权相似度。之后,基于该度量快速聚合当前节点及其邻居节点以形成初始社区,并对社区进行扩展。在第三阶段,针对初始划分中可能出现的两两节点组成的小社区问题,以最大化加权网络模块度为目标进行社区合并,从而得到更为合理准确的社区划分结果。再次,鉴于主流的基于相似性的链接预测算法仅单一地考虑节点自身属性或路径结构信息对于相似性的影响,在准确率和复杂度上难以均衡,且无法直接应用于加权网络,提出一种基于多路径传输节点相似性的加权网络链接预测算法STNMP。基于加权网络在某一时刻的静态快照,定义节点对的边权强度来度量两节点的局部相似性,定义路径相似性贡献来度量两节点的路径结构相似性。之后,有效融合局部相似性和路径结构相似性,定义了多路径传输节点相似性作为两节点的总相似度。随后的实验中,为达到较高预测准确率的同时有效降低复杂度,通过参数调整确定了最优路径步长的范围。最后,针对现有符号预测算法仅能完成缺失符号类型的已有边的符号预测,无法实现未来链接预测的问题,提出一种相似性与结构平衡理论结合的符号网络链接预测算法PSN_BS。基于连接两节点的步长为2和3的路径,有效融合节点的局部相似性和路径结构相似性,并在引入步长影响因子的基础上,定义了两节点基于结构平衡理论的边值预测得分。针对得分为0时无法预测符号的情况,引入节点负密度的概念,采用节点的度信息进行符号预测。最终,综合边值预测得分与节点负密度完成链接预测与符号预测。对于上述所提算法,通过实验验证了其正确性和有效性。