论文部分内容阅读
近年来,动态社交网络社区发现算法的研究逐渐受到人们关注,并取得了一些成果,但国内外关于动态社交网络的研究还只处于起步阶段,所提出的方法也很有限,因此,对于动态社交网络的研究就显得尤为重要。而社交网络中,虚拟社区结构的特征呈现多样性特点,重叠社区结构又是其中典型的代表,为此本文调研了国内外动态社交网络重叠社区发现问题研究的实际情况,发现动态社交网络重叠社区发现问题的研究极少,没有比较成熟和完善的解决算法,所以本论文研究围绕动态社交网络重叠社区发现问题展开,主要研究的内容如下:(1)建立动态社交网络模型。基于图的理论,我们根据社交网络中个体之间的联系,构造了社交网络拓扑结构的网络基图。由于社交网络的动态性,我们使用了一种离散时间序列上的网络模型框架,对所研究的动态社交网络进行建模,并给出了相应的数学模型描述。(2)网络中社区划分的聚类方式。对于动态社交网络在某个时刻的网络快照上的社区划分,我们采用了一种基于边(连接关系)的聚类方式来得到网络的重叠社区;对于时间序列上的不同时刻的社交网络,我们采用了一种具有平滑性和一致性的演化聚类框架,对动态社交网络整体进行聚类,使得我们在得到动态社交网络每个时刻网络的重叠社区划分时,保持相邻时刻网络结构的一致性和变化的平滑性。(3)目标函数设定。基于本论文研究的动态社交网络重叠社区发现问题中社区的可重叠性,还有对于社交网络的动态性我们使用了演化聚类的聚类方式,在选择目标函数时,我们选择了重叠社区模块度函数和Randindex指标作为目标函数,其中前者作为演化聚类中的聚类代价函数,后者作为演化聚类中的时空代价函数。(4)设计多目标优化算法。本文提出了一种用于解决动态社交网络重叠社区发现问题的基于演化聚类框架和连接关系聚类的多目标优化算法一一DNOCD-LMOGA算法。在DNOCD-LMOGA算法中我们对NSGA-Ⅱ算法步骤进行了简化和改进。此外,我们还设计了解的编码和解码方式,还有个体的交叉、变异和解的选择策略等。最后我们将提出的多目标进化算法在真实的数据集上进行了实验,对实验结果进行了对比分析,实验表明本文提出的多目标进化算法能有效的解决动态社交网络重叠社区发现问题。