基于归属度的社团结构发现算法研究

摘要

复杂网络的社团结构是复杂网络的一个重要拓扑特征，网络中的社团是网络中连接比较紧密的节点的集合，在社团内部节点间的连接比较紧密，社团与社团之间的节点连接比较疏松。根据复杂网络中节点间的逻辑关系来寻找网络中的社团结构的过程，就是复杂网络的社团发现。复杂网络的社团发现能够帮助更好的分析复杂网络中的功能模块，更深的理解复杂网络的拓扑特性，并能够有助于发现复杂网络的隐藏特性。复杂网络的社团发现对于计算机科学、社会科学等具有重要的意义，本文就复杂网络的社团发现做了如下工作:
　　(1)提出节点与社团的归属度定义。节点与社团的归属度就是节点的邻居节点属于社团的数目与节点邻居节点总数目的比值，节点与社团的归属度表明了节点与社团内部节点的连接紧密程度，本文提出的算法都是基于归属度的。
　　(2)提出了基于节点与社团的归属度的算法。只需要知道网络的局部信息，求得节点与已知社团的归属度，在与设定的归属度阈值比较后判定是否将此节点划分到已知社团。对于寻找已知节点所属的社团问题，本算法具有更大的优势。
　　(3)提出了边与社团归属度定义。从边的角度考虑，将社团视作关系比较紧密的边的集合，而不是通常定义的关系紧密的节点的集合。与此边直接相连的边中属于社团的边数和与此边直接相连的边的总数的比值就是边与社团归属度。
　　(4)提出了基于边与社团的归属度的算法。和基于节点与社团的归属度的算法相似，本算法也是只需要网络的局部信息，求得边与已知社团的归属度，与设定的归属度阈值比较后判定是否将此边连接到已知社团。

目录

声明

摘要

第1章 绪论

1．1 研究背景及意义

1．2 本文研究内容及组织结构

1．3 国内外研究现状

1．3．1 传统的社团发现算法

1．3．2 分裂算法和凝聚算法

1．3．3 重叠社团结构发现算法

1．3．4 基于局部信息的算法

第2章 相关理论知识

2．1 复杂网络

2．1．1 无权无向图

2．1．2 简单图

2．1．3 度与邻居节点

2．1．4 度分布

2．1．5 节点聚类系数

2．1．6 边的聚类系数

2．2 社团结构

2．2．1 强社团结构与弱社团结构

2．2．2 节点与社团归属度定义

2．2．3 边与社团归属度定义

2．3 社团结构发现算法检测标准

2．3．1 实际基准网络

2．3．2 人造基准网络

2．3．3 正确划分率

2．3．4 共同信息比较法

第3章 基于节点归属度的社团结构发现算法

3．1 节点与社团归属度定义

3．2 网络中初始社团的确定

3．3 归属度阈值

3．4 基于节点归属度的社团结构发现算法原理

3．4．1 算法过程描述

3．4．2 由19个节点构成的三社团网络

3．5 寻找已知节点的社团

3．5．1 算法过程描述

3．5．2 Zachary空手道俱乐部网络

3．6 实验与分析

3．6．1 College Football网络

3．6．2 人工网络

3．7 小结

第4章 基于边的归属度的社团结构发现算法

4．1 边的聚类系数

4．2 边与社团归属度定义

4．3 归属度阈值

4．4 基于边的归属度的社团结构发现算法原理

4．5 实验与分析

4．5．1 重叠性社团网络

4．5．2 Zachary空手道俱乐部网络

4．6 小结

第5章 总结与展望

5．1 总结

5．2 未来工作展望

参考文献

致谢

攻读硕士学位期间发表的论文