基于隶属度的社会化网络重叠社区发现及动态集群演化分析
2016-05-06左万利
国 琳,左万利,彭 涛
(1.吉林大学计算科学与技术学院,吉林长春130012;2.吉林大学符号计算与知识工程教育部重点实验室,吉林长春130012)
基于隶属度的社会化网络重叠社区发现及动态集群演化分析
国琳1,2,左万利1,2,彭涛1,2
(1.吉林大学计算科学与技术学院,吉林长春130012;2.吉林大学符号计算与知识工程教育部重点实验室,吉林长春130012)
摘要：社会化网络中节点的复合属性可能为临时或过时状态,并且节点拥有一定能力维持固有状态,所以不可单纯依据新增数据或节点现有特征确定社区划分.本文提出可重叠社区发现算法及集群动态更新方案,根据网络历史数据分析节点对原始集群的隶属程度,并结合新增数据确定节点变化趋势,实现网络结构分析及社区动态更新.本文分别在不同数据集中测试聚类效果,实验结果证明算法既保持对新增数据的敏感度,也防止了节点短暂特征或节点维持固有状态的能力对划分结果的负面影响.
关键词:社区发现;社会化网络;聚类;重叠社区;自适应算法
1引言
社会化网络中用户的多重社会属性导致用户可同时从属于多个社区,因此基于可重叠聚类的社区发现算法效果更佳.另外,社会化网络的实时动态性可导致节点经常出现短暂性特征,该特征将影响社区划分结果的稳定性.本文充分分析节点维持固有状态的能力,并判断新增数据变化程度,结合不同时期节点状态,综合确定社区划分方案.
本文所做工作分为以下几个方面:
(1)关联强度分析及权重设定.以被分析节点为中心节点,依据其相邻节点集合构建的网络计算节点权重,由此获得的权重表示节点被设定为中心节点的概率.
(2)隶属度分析.根据节点变化趋势和节点从属于原社区的能力,分析变化的数据是否导致节点自身状态和社区特征的改变.
(3)可重叠社区划分及集群动态更新.分析节点是否脱离固有状态及是否形成新的稳定状态,进而更新原有的划分结果.
2相关工作
社区发现[1]根据元素间的关联关系划分数据集为若干社区.社区中的用户通过兴趣、行为、社会属性等特征建立连接,分析社区划分结果可有效识别网络结构、精确分析用户角色.社会化网络分析[2,3]的一般方法为基于特征向量、稀疏矩阵、分区技术、小世界网络分析等.多数传统社区发现算法可处理静态数据,但由于网络的实时变化性使社区划分需适应动态数据,所以要求算法对变化数据既保证一定的适应性,又要求有较强的甄别临时特征的能力,因此社区发现算法不能仅局限于静态数据处理.
处理不同离散时间点的社区结构或根据不同时刻网络快照获得网络特征动态分析社区结构[4],为动态社会网络分析的主要研究方向.分析动态网络理论模型一般为自旋模型、同步算法、随机游走,其中依据扩散规律计算节点间距离和相互吸引能力分析动态网络变换趋势的随机游走理论的方法较多[2,5].将图信息转换成矩阵形式,通过矩阵分解、变换等方法分析节点间距离关系并实现不同集群的划分[6,7],其划分结果精确,并且便于执行多网融合及异构网络分析[8].这些传统聚类算法划分的集群是互不相交的,但社会网络中的节点拥有多重社会属性并导致多数节点从属于多个社区[9],因此传统聚类算法无法处理拥有复杂关系的网络节点.
由于用户通常同时属于多个网络,因此将节点划分到某一特定簇的算法不能满足社会化网络的现实要求.文献[10]构建模块函数将网络中节点映射到欧几里得空间,以构建重叠社区结构.文献[11]可检测高密度重叠网络和不重叠网络,发现重叠区域内节点连接密度更高,进而提出节点连接概率公式以识别社区.文献[6]分析节点对不同社区的从属强度或受控水平以确定节点划分到相应社区的合理性.通过社区的可重叠聚类算法将节点不唯一的划分到多个聚类中以体现用户多重社会特征,有利于全面分析用户在网络中的不同角色,以及发现社区间关联关系和重叠区域,使更合理描述网络架构.
3特征网络构建
用户关系分布图G=
3.1关联强度分析
分析用户对不同主题的关注情况生成用户-项目矩阵A,其中任意αi=(αi1,αi2,…,αir)表示矩阵A的第i行向量,αi描述用户i对r个项目关注次数.由于不同用户对不同主题关注程度和关注类型都不一致,因此为方便数据比较需统一矩阵中的度量标准,即计算用户对不同项目的关注度比,以方便不同用户间比较,计算公式为:
(1)
其中eic∈(0,1]描述用户i对项目c的关注程度.如果用户仅和一个主题有关联,则eic的计算结果为1,并且eic=1表示用户对主题的最高关注程度.如果用户没有产生任何社交数据,则eic的计算结果为0,说明该节点既不浏览信息也不产生数据,即不为网络提供任何贡献.
根据矩阵A构建描述用户关系图G.如果某两个用户存在共同兴趣,则G中该节点间存在边,并且根据边权重信息衡量节点关联强度.边权重计算公式为:
λc=1{Ic(i,j)}
(2)
(3)
其中式(2)为Heaviside方程,当逻辑判断为真时,其返回值为1,否则为0.Ic(i,j)判断节点i与j是否存在共同关注主题c.wij表示节点i和j的连接概率,其与用户i和j的相关主题的关注程度有关.由此G中的任意两个相连节点,都是通过关注共同主题而导致其存在边相连接的,因此如果两个用户共同关注主题越多,其连接权重设定值越大,所以式(3)表示通过不同主题建立连接的权重和.为方便数据比较将边权值设定在特定数值区间内,因此采用函数1-exp(-x)将变量x映射到(0,1)范围内.
3.2节点权重设定
计算节点权重时视当前分析节点为中心节点,以其邻接节点构成的网络(记为v-社区,其中v表示中心节点)为依据设定节点权重.节点v的权重受两个因素影响:(1)节点v与邻接节点的平均连接强度;(2)邻接节点间的关联密度.分别采用strength和density表示上述因素以计算节点权重,其计算方法分别如下所述.
v-社区关联强度:
(4)
其中│v.edge│表示节点v的邻接节点数量,∑v.edge表示连接节点v的边的权重和.
v-社区稀疏度:
(5)
(6)
其中│Com.edge│表示v-社区中节点间(包含节点v)存在边的数量,n表示v-社区中节点数量.v.sparsity为中间计算结果,表示v-社区的网络密度,但其数据表达不规范.因此v.density为稀疏度的最终度量参数,其将v.sparsity映射到(0,1)区间.
证明
v.sparsity分别与网络聚合系数和v的邻接节点数量呈正比关系,因此v.sparsity的计算公式为:
v.sparsity=v.net×|v.edge|
(7)
v.net为v-社区的聚合系数,其计算公式为:
(8)
(9)
为便于数据对比,将v.sparsity映射在(0,1)范围内,则最终计算公式为:
(10)
以度为1的节点为中心节点的网络应是低密度的,但根据上述公式计算的sparsity值为1,与实际要求不符,因此为该节点设定一个最低参数值以防止误认为是高密度网络,则公式适用条件为n≥2.
仅根据网络密度设定节点权重将导致社区密度大的中心节点权重大,而忽视了网络间的连接强度.因此综合v.density和v.strength参数,提出节点权重计算公式:
v.weight=η(v.density,v.strength)
(11)
根据density和strength对节点权重的不同影响程度设置η.在高密度网络环境下,节点权重更依赖于strength.相反在低密度网络环境下,节点权重更依赖于density.本文简单设置η(x,y)=(x+y)/2,均衡各参数对节点权重的影响程度[12].
图1(a)为全连接图,导致每个节点的权重计算结果相近,则最终影响节点权重的因素为节点间的连接强度.图1(b)为稀疏网络,比较节点7和节点9可知,虽然节点7的平均边连接强度较大,但由于其度为1,导致节点7的权重小于节点9.图1(c)近于正常的网络,节点权重受节点连接强度和网络密度的双重影响,经计算得知节点6的权重最大.
4社区动态划分
社区划分分为两个部分.根据已有的网络数据执行第一次社区划分,体现用户历史行为信息.第二次社区划分新增数据,根据节点对社区的隶属度和变化趋势实现社区动态划分.通常第一次划分是预先完成的工作,所以算法的总工作量是较小的,仅处理增量数据即可.
4.1社区划分及隶属度计算
第一次社区划分(算法1)根据节点权重选择当前网络的中心节点,并将该点的邻接节点加入网络,循环执行直到被发现的节点全覆盖或大部分覆盖网络时算法终止,合并多余的社区划分以简洁网络描述.第一次社区划分算法描述如算法1.
社区融合将被融合社区的所有节点加入覆盖范围更广的社区.由于density公式中分母的限制,可导致邻接节点少的节点比邻接节点多的节点的density值大,甚至大很多,因此可能产生多个小社区网络.本文根据节点数量衡量社区权威度,并用权威度衡量社区被单独划分的价值.当权威度小于阈值时允许节点和中心节点不完全覆盖的条件下与其他社区融合.
若节点在每个时隙过程中均以独立概率P接入信道，那么可以在退避过程中建立以时隙为单位的离散条件下的二进制退避阶数s(t)和碰撞窗口b(t)的马尔科夫过程[13]，如图4所示.
算法1的时间复杂度为O(mlog2m)+O(k(r+1)/2),其中m为节点数量,k为集群数量,r为集群内平均节点数量.
定义1核心节点:该节点与社区中大量节点存在高度关联关系.
定义2游离节点:从属于多个社区并且在每个社区中存在少量边的节点.
定义3普通节点:社区中除核心节点和游离节点外的其余节点.
核心节点存在极小概率迁移到其他社区,游离节点所属社区经常变化(注:与重叠区域的节点不同,游离节点可能在下一时刻完全被划分到新社区中),因此需分析节点对社区的隶属度,以确定节点变化趋势和维持原状态的能力.节点v针对某社区的隶属度受以下几个因素影响:(1)社区中节点v的邻接节点数量;(2)节点v的权重;(3)节点v与社区中心节点的距离;(4)节点v从属于的社区数量.综合上述,隶属度计算公式为:
节点v隶属于c-社区的程度为:
(12)
(13)
其中│v.adj│表示v的邻接节点数量,│Nv│表示v隶属于不同社区数量,len(v,c)表示v到c-社区的距离,即v到c的距离.p表示从v到c最短路径中的节点编号,p+1表示最短路径中p的下一个节点,wpq表示节点p与q之间边的权重.中心节点对社区的隶属度最高,因此中心节点的隶属度赋值为1.度为1的节点对社区的隶属度最低,但由于该节点只属于一个社区,导致其隶属度较高,可能误认为社区核心节点甚至中心节点,因此需赋予一个较低的隶属值,本文将其赋值为0.
4.2集群动态更新
P为m×n矩阵,用于描述m个用户对n个社区的隶属度.αu为P的某一行向量,表示节点u对n个社区的隶属度(式(8)).第一次社区划分生成隶属度矩阵Ppref,分析N时刻用户关系计算隶属度矩阵Pupdate.显然Ppref和Pupdate为维数不同矩阵,所以需统一Ppref和Pupdate维数.中心节点/非中心节点信息补充方案是在相应位置添加参数0,因为被补充的节点信息不出现在原矩阵中,所以仅增加原矩阵维度而不增加有效信息即可.经过处理后的矩阵记为T,其生成过程为:
(14)
其中exist(x,Y)判断向量x是否出现在矩阵Y中,如果是则返回1,否则返回0.
融合矩阵Ptrans:
Ptrans≜λTpref+(1-λ)Tupdate+Pre
(15)
(16)
(17)
其中Ptrans为节点隶属于不同社区的程度.λ为不同时期数据采集时间比值,即新增数据采集时间越长,其描述用户关系稳定性越强.节点有一定能力维持原状态,除非节点与原社区距离过远.根据随机游走原理分析用户回归原始状态的概率矩阵Pre,Pre的任意行向量βu表示节点u对不同中心节点维持原状态的能力.c∈(0,1)表示节点返回原始状态的概率,│Nr│表示节点r的边数量,Wpq表示节点p和节点q间边的权重.
举例计算图2中三种结构的Pre(s,e)值(设定c=0.2):
分析结果可知普通节点对中心节点的忠诚程度不仅受最短路径长度影响,同时受连接强度影响.
分析动态网络需间隔固定时间采集网络数据,当数据发生变化时,根据原始数据构建Tpref,其方法有两种:(1)执行第一次社区划分;(2)将先前建立的Ttrans直接赋给Tpref.通常采用方法2,仅在无先验知识条件下采用方法1,因此算法仅需处理新增数据构建Tupdate以计算Ptrans,进而执行第二次社区划分.
动态网络分析及集群动态更新算法描述如下:
degree(n,Com)根据节点n与集群Com的核心节点的平均距离计算其关联程度.函数DO-Cluster的时间复杂度为O(mlog2m)+O(k(r+1)/2)+O(m),其中m为Gn中节点数量,k为集群数量,r为集群内平均节点数量.
5实验
实验数据集为:MovieLens和Reuters数据集.对比算法为:非重叠聚类算法KMeans和可重叠聚类算法DClustR[12],ISC[13],Star[14],Gstar[15]和DHS[16].
表1 符号对照表
从MovieLens数据集中分别提取2385条用户信息和5000条用户信息构建数据集ML1和ML2.在ML1数据集上做KMeans和DO-Cluster对比实验,对比数据如表2所示.KMeans需设置随机种子取值和聚类数量,并经过多次迭代才能获得结果.从表2可知,KMeans算法设定的集群数量越多,则CSE值越小,但同时更易出现过度聚类情况.例如,在seed为5的前提下,numC分别设定为10和15的实验结果中都存在不必要的集群.DO-Cluster可重叠聚类结果适中,并不存在过度划分情况,也不需预先设定参数.表2说明DO-Cluster发现的集群没有对节点实现全覆盖,其原因是DO-Cluster为基于节点连接关系发现未处理节点,而存在一定数量的不活跃节点,因此需生成大量集群才能发现不活跃节点,但该集群中绝大部分节点都与已发现集群重叠,并且算法代价呈指数级别增加.所以将未被发现节点聚合为一个低频节点集群,其既弥补节点覆盖率低,又降低算法执行代价.
表3对比多个可重叠聚类算法和DO-Cluster的性能,其中FBCubed为综合精度和召回率的指标,可有效度量重叠聚类划分的准确度.数据集Reu-1、Reu-2和Reuter为从Reuters-21578中直接获取,Reu-Dy分为原始数据和新增数据以构建动态数据集.实验说明DClustR产生过多的不必要聚类结果,造成大量的重叠区域,然而DO-Cluster可最大化减少不必要的划分结果,以最少的社区划分达到最优的网络覆盖,处理不同类型数据集时算法效果稳定.
为进一步分析DO-Cluster划分结果,在ML2数据集上执行该算法,分析集群生成过程中数据的变化,实验结果如图3所示.
图3比较了17个集群信息,编号表示生成顺序.实验发现虽然c-1至c-8中节点数量较少,但集群内节点关联度高,导致中心节点权重较高,因此以该节点为中心的社区较早被发现.c-9的中心节点存在大量邻接节点,但由于网络密度较低,导致其中心节点权重不是最大的(注:c-9包含节点数量最多,发现未处理节点数量最多).通常集群内节点数量的增加导致较低的网络密度,这是c-9不被首先发现的原因.虽然c-15至c-17中节点数量较多,但未发现未知节点,即不增加有效信息,却增加集群间重叠范围,因此将其删除.综上,删除多余聚类结果后,c-1至c-14为DO-Cluster算法发现的社区.表4为社区内部节点分布情况.
表2 对比实验结果1
表3 对比实验结果2
表4 ML2划分结果分析
图4展示聚类结果中最大集群c-9的信息.c-9包含3099个节点,占整个网络61.98%的节点.ML2可由c-9发现大部分节点,再由其余规模较小的社区进行补充.具体网络度量指标如图5所示.
由图5(a)可知拥有边越多的节点数量越少,并且该集群的中心节点为拥有边最多的节点,其拥有3091条边.图5(b)、5(c)分别根据空间内元素间距离和节点特征值分析节点在图中的中心性度量.
c-12与c-14节点度的取值情况分布相似,即拥有大量边的节点数量较少,并且大多数节点拥有少量边.但c-13与c-12、c-14完全不同,其节点度取值分布平均,因此网络密度也较大.实验发现网络内节点数量较少时易达到网络内部高密度连接,而较大节点数量通常导致较低的网络连接密度,因此c-13的情况较难出现.
6结论
本文提出算法根据网络历史数据计算节点对社区的隶属程度，并结合新增数据确定节点变化趋势，运用可重叠社区划分算法实现网络结构分析及动态更新.该算法既保证对新增数据的敏感度，也防止节点临时特征对划分结果的负面影响. 实验验证了算法的可行性和社区划分结果的正确性，并说明如果仅根据节点覆盖率确定社区数量将导致重叠面积增加，而难以减少未被发现节点数量，因此节点不完全覆盖的划分结果是合理的.
参考文献
[1]Flake G W,Lawrence S,Giles C L,et al.Coetzee.Self-organization and identification of web community[J].Computer,2002,35(3):66-70.
[2]Thakur G S,Tiwari R,Thai M T,et al.Detection of local community structures in complex dynamic networks with random walks[J].IET Systems Biolpgy,2009,3(4):266-278.
[3]潘磊,金杰,王琮骏,等.社会网络中基于局部信息的边社区挖掘[J].电子学报,2012,40(11):2255-2262.
Pan Lei,Jin Jie,Wang Chong-jun,et al.Detecting link communities based on local information in social networks[J].Acta Electronica Sinica,2012,40(11):2255-2262.(in Chinese)
[4]Tantipathananandh C,Berger-wolf T,Kempe D.A framework for community identification in dynamic social networks[A].Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C].California,USA:ACM,2007.717-726.
[5]Wang W,Liu D,Liu X,et al.Fuzzy overlapping community detection based on local random walk and multidimensional scaling[J].Physica A:Statistical Mechanics and Its Applications,2013,392(24):6578-6586.
[6]Christiano T,Zhao L.Uncovering overlapping cluster structures via stochastic competitive learning[J].Information Sciences,2013,247:40-61.
[7]Wang C-D,Lai J-H,Yu P S.NEIWalk:Community discovery in dynamic content-based networks[J].IEEE Transactions on Knowledge and Data Engineering,2013,26(7):1734-1748.
[8]Comar P M,Tan P-N,Jain A K.A framework for joint community detection across multiple related networks[J].Neurocomputing,2012,76(1):93-104.
[9]Fortunato S.Community detection in graphs[J].Physics Reports,2010,486(3-5):75-174.
[10]Zhang S,Wang R,Zhang X.Identification of overlapping community structure in complex networks using fuzzy cc-means clustering[J].Physica A:Statistical Mechanics and Its Applications,2007,374:483-490.
[11]Yang J,Leskovec J.Overlapping community detection at scale:A nonnegative matrix factorization approach[A].Proceedings of the 6th ACM International Conference on Web Search and Data Mining[C].Roman,Italy:ACM,2013.587-596.
[12]Perez-Suarez A,Martinez-Trinidad J F,Carrasco-Ochoa J A.An algorithm based on density and compactness for dynamic overlapping clustering[J].Pattern Recognition,2013,46(11):3040-3055.
[13]Pons-Porrata A,Ruiz-Shulcloper J,Berlanga-Llavori R,et al.Un algoritmo incremental para la obtención de cubrimientos con datos mezclados[A].Proceedings of the 7th Iberoamerican Conference on Pattern Recognition[C].Mexico:CIARP,2002.405-416.
[14]Aslam J,Pelekhov K,Rus D.Static and dynamic information organization with star clusters[A].Proceedings of the 7th International Conference on Information and Knowledge Management[C].Bethesda,Maryland,USA:ACM,1998.208-217.
[15]Pérez-Suárez A,Medina-Pagola J.A clustering algorithm based on generalized stars[A].Proceedings of the 5th International Conference on Machine Learning and Data Mining in Pattern Recognition[C].Leipzig,Germany:Springer,2007.248-262.
[16]Gil-García R,Pons-Porrata A.Dynamic hierarchical algorithms for document clustering[J].Pattern Recognition Letters,2010,31(6):469-477.
国琳女,1987年8月生于吉林吉林,2013年至今于吉林大学计算机学院攻读博士学位,从事社会化网络、知识挖据及搜索引擎有关研究.
E-mail:guolin13@mails.jlu.edu.cn
左万利(通讯作者)男,1957年12月生于吉林省吉林市,现为吉林大学计算机科学与技术学院教授、博士生导师,ACM职业会员,从事数据库、Web智能、网络搜索引擎、自然语言处理等有关研究.
E-mail:wanli@jlu.edu.cn
Overlapping Community Detection and Dynamic Group Evolution Analysis Based on the Degree of Membership in Social Network
GUO Lin1,2,ZUO Wan-li1,2,PENG Tao1,2
(1.CollegeofComputerScienceandTechnologyofJilinUniversity,Changchun,Jilin130012,China;2.SymbolComputationandKnowledgeEngineerofMinistryofEducationofJilinUniversity,Changchun,Jilin130012,China)
Abstract:The complex social attributes of nodes in the network have a certain ability to maintain the former state,so it is inappropriate to determine community division merely based on newly added data.This paper proposes an overlapping community detection algorithm and dynamic cluster update strategy,which,by fully analyzing historical network data to compute the degree of nodes belonging to communities,determines the evolution tendency of nodes through incorporating incremental data to analyze the structure of the network and update the division results automatically.Experiments on several typical datasets demonstrate that the algorithm not only ensures the sensitivity to incremental data,but also avoids the negative effect of temporary features in maintaining intrinsic states on the clustering results.
Key words:community detection;social internet;clustering;overlapping community;adaptive algorithm
作者简介
DOI:电子学报URL:http://www.ejournal.org.cn10.3969/j.issn.0372-2112.2016.03.014
中图分类号:TP391
文献标识码：A
文章编号：0372-2112 (2016)03-0587-08
基金项目:国家自然科学基金(No.60973040);国家自然科学青年基金(No.61300148);吉林省重点科技攻关项目基金(No.20130206051GX);吉林省科技计划青年科研基金(No.20130522112JH);中国博士后基金项目(No.2012M510879);吉林大学基本科研业务费科学前沿与交叉项目(No.201103129)
收稿日期:2014-06-07;修回日期:2014-10-15;责任编辑:覃怀银
