基于关联系数的社区划分算法研究

"基于关联系数的社区划分算法" 本文提出了一种基于关联系数的社区划分算法，旨在克服模块度Q值只适用于无向无权网络的缺陷，并且更符合社区结构的定义。该算法通过计算社区内部连接强度和外部连接强度的关联系数来评判社区划分的好坏。 社区结构是指网络中节点之间的连接关系，社区结构的研究迄今已有很长历史，学者们已研究出多种划分算法，如GN分裂算法、Newman快速算法、基于Laplace矩阵的谱平分算法、Kernighan-Lin算法等。这些算法有一共性：用模块度量Q作为算法终止条件，同时也作为衡量社区划分好坏的标准。 然而，模块度Q值只适用于无向无权网络，对于有向有权网络的社区划分算法则无能为力。因此，提出了基于关联系数的社区划分算法，该算法可以克服模块度Q值的缺陷，并且更符合社区结构的定义。 关联系数是指两个曲线在同一时刻的相似度，可以用来评判社区内部连接强度和外部连接强度的相似度。通过计算关联系数，可以直观地符合社区结构定义，两者的关联系数越小，同时内部连接值越大，之间连接值越小，则划分结果越好。 在本文中，我们首先阐述了在划分算法中占重要位置的关联系数，然后提出基于此的算法，最后将算法实验于城市社区划分应用场景，并将本文算法与基于Q值的社区划分算法结果进行比较，结果表明本文提出的算法是切实可行且有效的。 社会网络结构相关定义： 社会网络结构是指网络中节点之间的连接关系，可以用信息图表示。信息图包含n个节点的图G=（V，E，M），V是节点集合，节点vi有属性集VA={va1，va2，…，vam}。E是边集合，边ei有属性集EA={ea1，ea2，…，eal}。M为两节点共享邻居节点数的矩阵，简称共邻矩阵，矩阵元素Mij=eikekj，其中eik、ekj分别表示vi和vj之间是否存在链接。 信息图的连接强度矩阵元素Aij表示vi和vj的连接强度，它综合了节点属性、链接属性和共邻属性。 关联系数定义： 设有曲线sin（t）和cos（t），取t=0，1，2，…，10时刻的正、余弦序列{sin（0），sin（1），…，sin（10）}，{cos（0），cos（1），…，cos（10）}，则两曲线在各t时刻的关联系数如下：其中，（min）和（max）为两曲线在同一时刻对应的最小差和最大差。