学士本科毕设项目介绍。

社交网络社团发现算法

背景

对社交网络中的具有密集关系的节点所形成的社团进行发现，社团发现算法主要研究对象为无向图网络，而现实中很多问题为有向图网络，本项目研究了新的基于信息传递增益（ITG）的有向图社团发现算法。

算法介绍

通过对有向图网络中的最基本节点结构——三节点结构进行基于信息传递增益的建模，共统计出27种基本构型，通过对27种的对称性合并，共得到15种各不相同的独立情况。将在三节点结构向社团结构扩展，构建社团内，社团间的信息传递增益模型。算法实现上，第一步通过对节点的聚类系数进行排序并依次以高聚类系数及其邻居作为社团进行初步划分，第二步通过迭代计算节点在转移到各个社团时新的信息传递增益模型的变化，进行社团发现的微调。

算法评价

在多个维度对ITG算法进行评价，包括：社团个数，模块度，Jaccard系数（交集与并集之比），F-measure。

数据集

节点个数为几百左右，边条数为几千到一万左右

分布式实现

算法初步用JAVA实现，分布式部分使用scala语言，基于Spark框架。分布式部分仅在单机上实现。