基于边密度的复杂网络社区结构划分方法

针对基于模块度最优的社区结构探测算法会产生分辨率限制、时间复杂度高等问题,提出一种基于边密度的社区结构探测算法。该算法不仅可以对网络进行社区结构的划分,而且不会产生分辨率限制的问题,算法的运行复杂度是O(k·m),其中m为网络中的边数,k为网络中节点的最大节点度。为了验证该算法的正确性和性能,与著名的社团探测算法——GN算法和NF算法进行比较,结果表明所提出的算法是有效可行的。

图上合作博弈和图的边密度

1977年,Myerson建立了以图作为合作结构的可转移效用博弈模型(也称图博弈),并提出了一个分配规则,也即"Myerson值",它推广了著名的Shapley值.该模型假定每个连通集合(通过边直接或间接内部相连的参与者集合)才能形成可行的合作联盟而取得相应的收益,而不考虑连通集合的具体结构.引入图的局部边密度来度量每个连通集合中各成员之间联系的紧密程度,即以该连通集合的导出子图的边密度来作为他们的收益系数,并由此定义了具有边密度的Myerson值,证明了具有边密度的Myerson值可以由"边密度分支有效性"和"公平性"来唯一确定.

基于关键字密度的XML关键字检索

关键字检索具有友好的用户操作体验,该检索方式已在文本信息检索领域得到了广泛而深入的应用.对XML数据采用关键字检索是目前研究的热点.基于查询语义的XML关键字检索方法存在返回大量与用户查询意图无关的查询片段或者丢失符合用户查询意图的片段这两个问题.针对这些问题,在考虑LCA横向和纵向两个维度的基础上,提出了用户查询意图与LCA相关性的两个规则,根据两个规则定义了LCA的边密度和路径密度,建立了综合的LCA节点评分公式,最后设计TopLCA-K算法对LCA进行排名,并利用中心位置索引CI提高了TopLCA-K算法的效率.实验结果显示,利用所提出的方法返回的查询节点更加符合用户需求.

基于增广边簇序列的重叠层次社区发现

高质量重叠层次社区的挖掘和发现已成为社会网络研究热点,为更有效地发现社会网络中具有重叠层次性的社区结构,提出基于增广边簇序列的边社区发现算法(DLC_ECS).在产生包含所有可能密度参数对应的社区结构的增广边簇序列的基础上,找出全局最优的密度参数,发现全局最优的边社区结构,将识别的边社区结构转化为节点社区结构,发现具有重叠结构的社区.在该序列的基础上,提出层次边社区提取算法(HLCE_ECS),快速发现序列中的层次边社区结构,将识别的边社区结构转化为节点社区结构,发现同时具有重叠和层次结构的社区.在真实数据集和人工数据集上的实验表明,DLC_ECS具有更高的社区发现质量,HLCE_ECS能发现有意义的层次边社区结构.

随机图的最大独立集

文章主要介绍了用非贪婪算法在由顶点数和基准边密度赋值生成的不同类型的随机图上进行求最大独立集的测试,通过对测试结果的分析得出顶点数、边密度、基准边密度与独立数、运行时间的联系。