重叠社区结构的挖掘算法

针对大多数社区挖掘算法致力于寻找独立不相重叠的社区结构,而实际的网络中,社区结构往往是重叠的问题。基于凝聚方法和贪婪算法原理,提出了一种新的算法来挖掘社会网络中彼此重叠的社区结构。在模拟数据集和标准测试数据集上的实验结果表明了算法的可行性和有效性。     

基于差分演化的复杂网络社区挖掘算法研究

社区结构的挖掘问题已经成为复杂网络中重要的研究方向,其挖掘算法是关键的核心问题.为了提高对社区结构进行挖掘的准确度,提出一种基于差分演化思想的复杂网络社区挖掘算法(Differential Evolution Community Detection Algorithm,DECD).DECD算法设计了一种新的编码方式,以模块密度函数作为优化目标,通过差分演化算法对复杂网络实施有效划分.实验结果表明,新的编码方式提高了编码速度并解决了社区重复编码问题,同时DECD算法能够提高复杂网络中的社区结构挖掘的准确度.     

基于概率主题模型的社交网络层次化社区发现算法

针对传统的社区发现算法大多基于网络拓扑结构寻找独立的社区结构,忽略了用户兴趣属性,并且不能有效地发现社区间的相关性和层次关系等问题。该文提出一种新型的基于PAM(pachinko allocation model)概率主题模型的层次化网络社区发现算法,综合考虑了用户的兴趣和用户的社交网络关系,在同一模型平台上实现层次化的社区结构发现和用户兴趣挖掘,并捕捉和揭示社区之间的关联性和重叠性等特征。模型采用Gibbs采样方法进行参数推导。在真实数据集上的实验结果验证了所提出算法的可行性和有效性。     

基于环路紧密度的复杂网络社区挖掘方法

提出了一种基于环路紧密度的复杂网络社区挖掘算法(LTA):首先提出一种快速发现网络环路和计算其紧密值的算法,然后根据环路紧密值将网络聚类,再次揭示网络环路与社区结构的联系。并使用人工合成网络和真实网络数据集对LTA进行了验证,实验结果证明了LTA对复杂网络社区挖掘问题的有效性和高效性。     

基于传播影响力的重叠社区划分算法

在研究经典标签传播算法的基础上,提出了一种基于传播影响力的重叠社区划分算法COPRA-PI,可用于挖掘加权网络中的社区结构。该算法在COPRA算法的基础上从节点影响力、边影响力、历史标签影响力3个方面综合考虑传播影响力;同时针对COPRA算法中每个节点在每次迭代过程中均具有相同的最大标签数,且该最大标签数目需手动设置等不足,该算法中设计了一个自适应的最大标签数。实验结果表明,COPRA-PI算法在经典的数据集上对比现有经典算法更能挖掘出高质量的社区结构且收敛速度较快。     

电信网中基于社区挖掘的用户行为预测算法

利用社会网络分析去解决电信网中的用户行为预测问题,把用户行为预测转换为社区挖掘和社区内用户行为预测2个步骤。之后,利用改进的凝聚层次聚类算法实现了电信网中用户的社区挖掘,通过对社区内的邻近度进行排序,设计了社区内用户行为的预测算法。仿真实验结果表明,该算法能够有效的预测出指定社区中的用户行为。     

基于零模型的社区检测基准网络构造及应用

社区检测对于探索挖掘复杂网络的结构特性具有重要意义,社区检测算法性能对于检测结果具有重要影响。目前用于衡量社区检测算法性能的基准测试网络较为单一,主要包括人工合成网络和真实世界网络。由于真实世界网络中通常缺乏已知社区结构信息,人工合成网络成为衡量算法性能的主要途径,但普遍存在网络微观特性不可调且与真实世界网络差异较大、对检测算法区分度不高、无法更改局部网络结构等问题。为提升人工合成网络性能,该文提出基于零模型的基准测试网络构造方法,首先设计了能够保持中尺度特性的零模型,提升网络微观特性调整灵活度,使其更逼近真实世界网络结构特性;其次设计了能够调整社区结构强弱的零模型,提升网络社区检测的评价准确性;最后设计了能够调整局部拓扑结构的零模型,有效衡量局部社区结构特性变化对于整体网络结构及检测算法性能的重要性。实验结果表明,基于零模型的构造方法能够有效提升基准测试网络的多样性和灵活性,更加逼近真实世界网络特性,因此更能满足对于社区检测算法性能的评价需求,对于提升复杂网络社区检测性能具有重要意义。     

一种基于非对称三角形割的重叠社区发现算法

发现由相似功能的个体所形成的社区结构是复杂网络分析的重要任务之一. 提出一种基于非对称三角形割的重叠社区发现算法,首先根据社区内三角形连接情况对社区质量进行评价,并根据节点与社区的三角形连接定义了节点对社区的归属度和连接强度. 考虑到网络不同部分连接密度的差异,在将节点从社区中移除或加入社区的过程中,为每个节点分别设置了不同的移除阈值和扩展阈值,以提高社区发现质量. 将每个节点与其邻居节点组成初始社区,将归属度低于移除阈值的边缘节点从社区中移除,将连接强度高于扩展阈值的外围节点加入社区,社区节点移除和扩展阶段迭代进行直至社区结构趋于稳定,最后去掉重叠率过高的社区得到最终结果. 在7个带社区标签的网络上将所提算法与其他7个经典重叠社区检测算法进行比较,通过重叠标准互信息和F₁指标进行评价,结果表明所提算法可以较好地发现不同规模网络中的社区结构.     

基于结构相似度的多尺度局部社区发现算法

社会网络规模巨大且结构动态变化给传统社区发现算法带来了巨大挑战,局部社区算法通过种子节点进行扩展得到局部社区,较好解决了这些问题。结合节点结构相似度在传统社区定义的基础上提出了一种新的社区定义,在该定义基础上引入尺度因子并定义了结构模块度,基于该模块度提出了一种多尺度局部社区发现算法,并改进该算法使之应用到局部重叠社区发现。通过实验选择效果较好的节点结构相似度,在真实网络中和其他局部社区发现算法进行对比实验,结果表明该算法具有较好的性能。     

垂直分布下的隐私保护频繁闭合项集挖掘算法

针对垂直分布下的隐私保护关联规则挖掘算法效率低、安全性不高的问题,提出一种隐私保护频繁闭合项集的挖掘算法。算法利用挖掘频繁闭合项集代替频繁项集,IT-Tree作为搜索空间,Diffsets作为压缩结构,采用基于RSA可交换加密算法的隐私保护集合差集协议。实验结果表明,算法具有较好的隐私性、准确性、高效性。     

校园移动社交网络中基于种子的数据分发算法

为了研究如何利用节点间间歇性连接传输数据,提出了校园移动社交网络中基于种子的数据分发算法,其主要思想是为每一个社区选择一个种子节点,并利用种子节点来进行数据分发.仿真实验表明,与著名的Epidemic、PS和SGBR算法相比,该算法可明显地降低网络开销,同时接近Epidemic算法达到的最大传递率.     

集合扩充的社团分解算法

社团结构是复杂网络的重要特征之一,寻找网络中的社团对于分析整个网络的结构和功能都有非常重要的意义.综述了一些经典的复杂网络社团结构划分的算法,提出了一种基于集合扩充的社团结构划分的新算法.该算法以网络中相邻的两个节点构成的集合为起点,用社团同外部联系的边的数目与社团内部边的数目的比值作为度量指标,通过计算将某一个邻居节点加入该集合后度量指标值的变化情况来判断某个邻居节点是否加入该集合,若度量指标值变小则将该邻居节点加入该集合,若度量指标值变大则不将该邻居节点加入该集合,直到不再有新的邻居节点加入时,一个社团就被划分出来.在剩下的网络中重复这个过程直到网络中的节点完全被划分.用社团结构分解中的两个经典例子测试了该算法,从测试结果来看,用该方法能够合理地划分网络中的社团结构,且运算量小,运行效率高,达到了预期目标.该社团结构的划分方法对于规模较大的复杂网络也具有普遍意义.     

小世界效应加速生物地理学优化的社团识别算法

为提高基于优化方法的网络社团结构识别算法的有效性,设计一种利用小世界效应加速生物地理学优化过程的网络社团结构识别算法. 首先基于矩阵随机编码建立网络社团识别生物地理学优化框架,在栖息地中全局进化地搜索对应于最大化模块度的网络社团划分. 然后,给出基于小世界效应的生物地理学迁移策略,可以加速进化算法的信息交换过程. 最后,运用该算法在现实网络和人工合成网络上进行实验. 结果表明:引入小世界效应能够降低网络社团结构识别算法的收敛时间;在典型现实网络与人工合成网络上运行该算法能够获得较高的模块度值与标准化互信息值;信息交换的拓扑结构能够优化进化算法效率. 应用小世界效应加速生物地理学优化的网络社团识别算法具有较好的可行性与有效性.     

密度峰值聚类的自适应社区发现算法

为减少社区发现算法中参数的选择对社区划分的影响,同时使算法能够自适应地进行社区划分,本文提出一种基于核密度估计的密度峰值聚类的社区发现算法KDED.首先,定义一种基于信任度的距离度量,将社交网络中的用户关系量化为距离矩阵,使用矩阵元素的大小度量用户关系的紧密程度;然后对距离矩阵进行核密度估计,统计各个节点在网络中的影响大小,结合热扩散模型改进计算流程,使其自适应不同规模的数据集以提高计算精度;结合密度峰值聚类原理和社区属性确定社区中心节点后,可根据节点间的距离得到社区内部层次结构和社区外部的自然结构;最后将剩余节点按距离分配到相应的社区当中以完成社区划分.仿真结果表明:通过可视化软件可观察到,通过KDED算法得到的社区划分结果具有清晰的自然结构和内部层次结构;随着社区规模的提升以及划分难度增加,KDED算法具有出色的稳定性;在真实数据集以及LFR基准网络上均得到较为接近真实划分结果的社区划分,自适应性良好,验证算法的可行性与有效性.     

Community discovery method with uncertainty measure of overlappingnodes based on topological potential

Community discovery of complex networks,esp.of social networks,has been a hotly debated topic in academic circles in recent years.Since actual networks usually contain some overlapping nodes that are d...     

基于萤火虫算法的脑效应连接网络学习方法

脑效应连接网络学习是人脑连接组研究的一个重要研究课题,准确识别脑效应连接网络对于脑疾病的早期诊断以及病理研究具有重要意义.本文将萤火虫算法与贝叶斯网相结合,提出了一种带有繁殖机制的脑效应连接网络萤火虫学习方法.新方法使用K2评分作为目标函数来衡量萤火虫个体的绝对亮度,利用萤火虫种群的寻优来完成脑效应连接网络的学习,并利用繁殖机制对种群实施进一步的优化.首先将一种仅含少数边的脑效应连接网络表示成一个萤火虫个体,并通过萤火虫个体的定向移动操作以及随机移动操作逐步构建脑效应连接网络;然后每经过一定代数的寻优后,萤火虫种群执行一次繁殖过程,以优化效应连接网络的质量.最后,当算法收敛时,将萤火虫种群中绝对亮度最高个体所代表的网络结构作为学习到的最优脑效应连接网络.在多组模拟数据集上的实验结果验证了新算法中繁殖机制的有效性,且与其它算法相比,新算法具有明显优势.在真实数据上的实验也表明了算法的潜在实用性.     

社会困境下双重度偏好社团网络合作涌现研究

考虑复杂社会网络中的“社团结构”特征,基于经典的囚徒困境博弈和累积收益策略更新规则,构建社会困境下具有双重度偏好的社团网络演化博弈模型,系统研究静态社团网络外部连接密度、动态社团网络中策略与结构共演化时间尺度以及策略更新中噪声对合作涌现的影响及其作用机理。研究发现,社团网络间连接密度对合作涌现具有负向影响;尽管静态社团网络合作水平在数值上是明显高于动态社团网络,但其合作演化的策略构成、策略稳定性及其演化动态性存在显著差异;动态社团网络中策略与结构共演化的时间尺度对合作涌现的影响呈现相对优劣互转的变化趋势,具体表现为在低背叛诱惑值下时间尺度越小越不利于合作,而在高背叛诱惑值下时间尺度越小越有利于合作;策略更新过程中噪声对静态和动态社团网络合作涌现的影响是单调的,且适度的引入噪声能够显著提高合作水平。