基于进化算法的局部社团结构发现及其在推荐系统上的应用

摘要

目前，随着网络越来规模的越来越大或者网络是个动态增加的网络，网络的完整信息往往是很难获得的，如网络网页、科研论文和脸谱网用户，从这些网络中得到完整的社区划分信息是不现实的，此外，网络中往往存在一些对网络结构和功能其关键作用的节点，首先把这些节点找到，那么对网络结构的分析有重大帮助。如果把网络中的节点都考虑在内对网络进行整体划分，一方面这将会花费很多的时间，另一方面这将得到很多冗余信息，不利于对网络的结构进行分析，在这种情况下局部社团检测更加有意义，局部的社区结构可以提供我们许多微观分析，可以是宏观分析的辅助分析，然而大多数局部社团检测对初始点比较敏感，初始点的选择不同可能会影响最后的结果不同。本论文提出的基于进化算法的局部社团检测算法，首先是发现网络中的“核”，然后再基于这个“核”进行扩展，这样就解决某一初始节点位置不同会影响社区发现的结果的缺点。随着现实生活中计算机网络技术的技术进步，网络作为电子和商业交易媒介的重要性日益增加，这促使了推荐系统技术的发展。本论文主要研究基于进化算法的对局部社区检测问题，并把所提出的基于离散粒子群的的局部社区检测方法应用到推荐系统问题上，主要的工作总结如下：
　　（1）提出了一种基于文化基因算法提取最密集的社会网络社团结构算法（A Memetic Algorithm for Extracting the Tightest Social Network Community），Memetic Algorithm是由进化算法演变过来的优化算法,它是把在种群中的进行全局搜索和在个体中进行局部启发式搜索进行组合的算法。为了得到最密集的社团结构，该算法对网络连接图进行全局搜索，克服了传统从某单一节点发现社团结构的缺点，同时为了使结果更加准确，设计一个启发式算法来进行局部搜索。通过实验对比，该算法能得到较好的社团结构。
　　（2）提出了一个基于多智能体遗传算法并扩展最密集节点来发现局部社团结构算法（A Multi-agent Genetic Algorithm for Local Community Detection by Extending the Tightest Nodes），该算法记为MAGA-LC。多智能体遗传算法是基于种群的智能优化算法，其中的智能体能够作用于环境，即通过自身的行为改变环境，智能体之间还可以进行通信，这样使得多智能体之间比较容易进行协作进行搜索，以使种群朝着最优化方向进行发展，为了得到局部范围内网络连接图中最密集的节点，这些最密集的节点我们把它叫做这部分网络的“核”，设计了一个邻域交叉算子，该算子使算法在局部范围内具有更好的全局搜索的能力的特点，这就解决了随机初始节点对结果造成的误差影响，其次在找到这个“核”之后，再对其进行扩展得到局部社区，在实验中，我们把该算法与几个传统的局部社区发现算法进行对比，实验结果表示 MAGA-LC有很好的表现。
　　（3）很多实际应用的推荐系统都是采用协同过滤推荐技术来执行推荐的，但是当用户数目相对于项目数目很少的时候，用户对项目的评分比较少，此时无法把协同过滤技术准确应用到推荐系统上，但是，通过网络技术，把相似的用户划分到一个社区内，基于社区进行协同过滤来进行推荐，能一定程度解决上述问题。设计了一个基于离散型的粒子群优化（Discrete particle swarm optimization）的局部社区检测算法，该算法记为 DPSO-LC。在实验中，该算法首先进行社区检测实验，算法能得到较高的归一化互信息指标值，然后，算法进行协同过滤实验，并与两个协同过滤推荐系统算法进行比较，实验结果说明我们设计的基于离散粒子群优化的局部社区检测协同过滤推荐方法有较好的表现结果。

目录

声明

插图索引

表格索引

符号对照表

缩略语对照表

第一章 绪论

1.1课题的背景和意义

1.2研究现状

1.3论文内容结构安排

第二章 复杂网络问题研究及相关算法

2.1复杂网络

2.2经典的社区检测方法

2.3进化计算

2.4遗传算法简介

2.5本章小结

第三章 基于文化基因算法提取最密集的社会网络社团结构算法

3.1文化基因算法

3.2社会网络

3.3相关工作

3.4 MA-TSNC

3.5实验结果

3.6本章小结

第四章 基于多智能体遗传算法并扩展最密集节点来发现局部社团结构

4.1局部社区概念

4.2相关工作

4.3多智能体进化模型简介

4.4 MAGA-LC

4.5实验结果

4.6本章小结

第五章 基于离散粒子群优化的局部社区检测协同过滤推荐方法

5.1推荐系统背景技术介绍

5.2局部社区检测与协同过滤技术结合

5.3算法步骤

5.4实验

5.5本章小结

第六章 总结与展望

6.1本文工作总结

6.2展望

参考文献

致谢

作者简介