基于CPM算法的社团演化研究

摘要

DBLP学者合作网络作为最早研究的复杂网络之一，其海量的数据为相关的研究提供了有力的支持。DBLP网络分支数据量庞大，总体研究难度较大。用改进的CPM扩展核心架构的算法切割网络分支，使所有节点都有社团归属，得到的社团数量和规模分布相对合理。计算社团之间的传承关系，得到社团演化的分支。
　　社团在演化过程中会出现融合和分化的情况，本文主要比较演化过程中不同结构的合作关系社团的结构稳定性和结构数量，和不同结构社团的规模增长情况。首先，根据相邻年份之间社团的传承关系得到9465个社团演化分支，计算不同结构社团随年份演化的数量增长情况。其次，根据社团演化分支的演化特点，给出BA结构社团演化过程中结构和规模变化情况，分析BA结构社团的演化特点。从1977年的12号分支的3个BA社团到2010年的3631个BA结构社团，有5320次非BA演化成BA结构社团，有4494次BA演化成非BA结构，有19461次保持BA社团的结构不变。然后，选取80个起始社团都是BA结构的社团演化分支，和DBLP社团演化分支中起始演化结构为9个ER随机结构和3个BA结构社团作比较。演化成BA结构社团的平均增长率和增长概率分别为0.00297和0.491，低于DBLP的0.297和0.574。保持BA结构不变和非BA结构演化成BA结构的概率分别是0.925和0.443，高于DBLP的0.812和0.142，不同起始结构的社团对社团演化结构和规模指标会产生影响。最后，计算演化成不同结构社团的平均增长率和增长概率，和结构演化概率。演化成BA结构的平均增长率是0.267是非BA结构的0.0401的6倍多，增长概率是0.574比非BA结构的0.333高出24.1％。保持BA结构不变的概率是0.812只比最高的完全规则结构的少2.2％，非BA结构演化成BA结构的概率是0.142，只比最高的ER随机结构少3.9％。
　　综合不同结构社团的演化数据，BA结构社团的结构演化概率较高，演化成BA结构社团的平均增长率和增长概率都高于其他结构的社团。BA结构社团在演化过程中具有结构增长较快，规模增长最快，结构稳定性良好的优势。通过大量的数据集计算，对DBLP学者合作网络的内部演化关系有进一步的了解，预测网络结构的变化。推测网络的演化趋势，对科学研究活动起到一个指导作用，甚至可以优化合作结构，进而推动相关的发展。

目录

声明

摘要

第1章绪论

1．1研究背景

1．2社团演化研究的意义

1．3社团演化研究现状

1．4论文组织结构

第2章DBLP时态网络和社团发现

2．1四种基础结构类型网络

2．1．1规则网络

2．1．2随机网络

2．1．3小世界网络

2．1．4无标度网络

2．2 DBLP时态网络

2．2．1 DBLP形成过程

2．2．2数据库的设计

2．2．3 DBLP网络构建的基本过程

2．3社团发现算法

2．3．1 CPM社团发现算法基本原理

2．3．2 CPM算法实现和改进

2．3．3改进的CPM算法得到的社团

2．4社团结构的判定算法

2．4．1幂率拟合判定社团结构

2．4．2实验结果和数据分析

2．5 CPM切割DBLP网络得到的社团结构和规模

2．5．1网络的度分布图

2．5．2分割得到的社团结构

2．5．3时态网络每年不同结构的社团规模

2．6本章小结

第3章社团的演化过程

3．1社团的传承关系

3．1．1社团演化分支的演化

3．1．2社团演化分支的时间跨度和规模变化

3．1．3社团演化分支的结构和规模变化

3．1．4社团演化分支局部规模变化

3．2 BA结构社团的演化过程

3．2．1 BA无标度社团的结构演化

3．2．2 BA结构社团的结构演化分类

3．2．3 BA社团结构演化的规模变化

3．2．4 BA结构社团的规模变化分类

3．3 BA结构社团的增长率

3．3．1 BA结构社团的增长率计算

3．3．2 BA结构社团年平均增长率

3．3．3 BA结构社团分支平均增长率

3．4 BA结构社团的演化

3．4．1演化成BA结构的平均增长率

3．4．2演化成BA结构社团的增长概率

3．4．3结构演化概率

3．5本章小结

第4章其他结构社团的演化

4．1 ER结构社团的演化

4．1．1结构演化概率

4．1．2平均增长率

4．1．3演化成ER随机结构社团的增长概率

4．2完全规则结构社团的演化

4．2．1结构的演化概率

4．2．2平均增长率

4．2．3演化成完全规则结构社团的增长概率

4．3 SW结构社团的演化

4．3．1结构演化概率

4．3．2平均增长率

4．3．3演化成SW结构增长概率

4．4不同结构与BA结构社团演化的比较

4．4．1结构的演化概率

4．4．2平均增长率

4．4．3演化成不同结构的增长概率

4．5本章小结

结论

参考文献

攻读硕士学位期间发表的论文和取得的科研成果

致谢