博文
review: 从链接密度遍历序列中挖掘网络社团的层次结构
||
从链接密度遍历序列中挖掘网络社团的层次结构
黄健斌, 孙鹤立, Dustin BORTNER, 刘亚光
黄健斌, 孙鹤立, Dustin BORTNER, 刘亚光
Journal of Software,2011,22(5):951−961
摘 要:
提出一种称为TRAVEL 的网络聚类算法.它能够产生包含所有可能密度聚类的网络链接遍历序列,并从
中自动发现网络的全局优化聚类.然后,遍历序列被转换为连续子区间堆结构.在此基础上,提出一种聚类算法
HCLU,可以无须用户干预地从连续子区间堆中自动发现网络的层次聚类边界.在真实网络以及计算机生成的仿真
网络数据集上的实验结果表明,所提出的算法比目前的基准方法具有更高的聚类精度.此外,算法能够从各种带有噪
声的网络中发现无冗余且鲁棒的层次社团结构.
中自动发现网络的全局优化聚类.然后,遍历序列被转换为连续子区间堆结构.在此基础上,提出一种聚类算法
HCLU,可以无须用户干预地从连续子区间堆中自动发现网络的层次聚类边界.在真实网络以及计算机生成的仿真
网络数据集上的实验结果表明,所提出的算法比目前的基准方法具有更高的聚类精度.此外,算法能够从各种带有噪
声的网络中发现无冗余且鲁棒的层次社团结构.
关键词: 基于密度的网络聚类;层次社团发现;中心点;离群点
网络社团发现
复杂网络社团发现方法基本思想: 多依据网络节点某种内聚性度量指标,递归对网络进行分裂或合并,挖掘其中社团结构
典型方法有:
(1) 图分割法.例如Kernighan- Lin、比例割、规范割、基于最大流的算法等.
(2) 谱聚类法.这类方法采用矩阵分析技术将求解图割函数转化为计算与分析图拉普拉斯矩阵的第二最小特征向量.
(3) 基于目标函数优化的聚类.这类方法通过最大化设定的聚类质量评价指标,寻找最优网络聚类.
the drawbacks of current work: 着重关注探测网络中的高密度子图,而忽略了对网络中其他角色节点的识别
author's work: 提出一种从网络的链接密度遍历序列中自动挖掘社团层次结构的新算法.
其主要创新点如下:
(1) 提出一种自动产生网络节点链接密度遍历序列的TRAVEL算法,既可保存所有可能ε参数对应网络结构信息,又可从中自动抽取优化参数ε对应的网络社团;
(2) 提出一种连续子区间堆结构,可从网络链接密度遍历序列中抽取所有连续ε区间及其嵌套层次结构;
(3) 提出一种HCLU 聚类算法,可从连续子区间堆中自动规约出合理的网络层次社团结构,并且分离出中心点和离群点.
(1) 提出一种自动产生网络节点链接密度遍历序列的TRAVEL算法,既可保存所有可能ε参数对应网络结构信息,又可从中自动抽取优化参数ε对应的网络社团;
(2) 提出一种连续子区间堆结构,可从网络链接密度遍历序列中抽取所有连续ε区间及其嵌套层次结构;
(3) 提出一种HCLU 聚类算法,可从连续子区间堆中自动规约出合理的网络层次社团结构,并且分离出中心点和离群点.
the organization of this paper:
1) 第1 节简单介绍基于密度网络聚类的基本概念.
2) 第2 节阐述链接密度遍历序列的提取算法,并给出全局优化参数ε的确定方法.
3) 第3 节给出社团层次结构规约算法.
4) 第4 节是实验结果及分析.最后,总结了全文.
1 基于密度的网络聚类
2 从网络的链接密度遍历序列中提取全局优化ε聚类
2.1 产生网络链接密度遍历序列
2.2 提取全局优化ε网络聚类
3 密度嵌套的社团层次结构提取
3.1 构建连续子区间堆
3.2 探测聚类边界
4 实验结果与分析
综合评测: TRAVEL+HCLU 算法 vs. 基于密度的网络聚类算法SCAN vs. 基于模块度优化的CNM和BGLL算法
4.1 实验数据集
真实网络数据集:US Political Books 网络 and DBLP 论文合著网络
4.2 评价指标
4.3 真实网络上的聚类性能评价
4.3.1 Polbooks 网络
4.3.1 Polbooks 网络
4.4 人工合成网络上的聚类性能评价
5 结 论
https://blog.sciencenet.cn/blog-468147-518544.html
上一篇：review: The service discovery methods issue: A web services
下一篇：review: Majority-vote on directed Erdos–Renyi random graphs
扫一扫，分享此博文