基于标签传播能力的改进LPA算法

㊃卫生服务评价㊃基于S E I R 模型对新发传染病住院患者变化规律的预测研究杨智博1, 刘珊珊2, 王聪2, 陈正举3, 蒋艳4ʌ基金项目ɔ 国家自然科学基金项目(72174135);四川省护理科研课题(H 21006)ʌ作者单位ɔ 1四川大学华西医院全程管理中心,四川成都,6100412四川大学华西医院循证护理中心,四川成都,6100413四川大学华西医院放射科临床磁共振研究中心,四川成都,6100414四川大学华西医院护理部,四川成都,610041ʌ通信作者ɔ 蒋艳,E -m a i l :h x h l j y@163.c o m ʌ摘要ɔ 目的 探求新发传染病发展规律,预测住院患者变化趋势,为今后应对突发公共卫生事件㊁评估医疗人力需求和制定疫情防控策略提供科学依据㊂方法 基于S E I R 模型理论,结合四川省新冠疫情防控政策,建立疫情传播过程中预警㊁暴发和恢复三个阶段的传染病动力学模型㊂根据四川省卫生健康委员会公布的新冠疫情实时数据,选取2020年1月21日-3月25日新冠病毒感染患者每日新增确诊病例数㊁累计确诊病例数㊁每日现有疑似病例数㊁累计出院病例数以及死亡病例数等,运用最小二乘优化问题算法,求解模型参数,输出模型拟合结果,从而评估模型可行性㊂结果 模型拟合曲线与实际参考曲线的整体变化趋势基本一致;预警阶段的平均绝对百分比误差为30.06%,均方根误差为17.8404;暴发阶段的平均绝对百分比误差为10.14%,均方根误差为66.8452;恢复阶段的均方根误差为16.5082㊂结论 该研究建立的多阶段S E I R 模型整体拟合效果较好,可以用于预测新发传染病住院患者人数的变化趋势㊂ʌ关键词ɔ 新发传染病; 传染病动力学模型; 住院患者; 新冠病毒感染ʌ中图分类号ɔ R 181.8 ʌ文献标志码ɔ A D O I :10.3969/j.i s s n .1673-5625.2024.02.023P r e d i c t i o no fC h a n g e s i nH o s p i t a l i z e dP a t i e n t sw i t hN e w l y E m e r g i n g I n f e c t i o u sD i s e a s e s b a s e d o nS E I R M o d e lY A N GZ h i b o *,L I US h a n s h a n ,WA N GC o n g ,C H E NZ h e n g j u ,J I A N G Y a n .*T h eW h o l eP r o c e s sM a n a ge m e n tC e n -t e r ,W e s tC h i n a H o s p i t a l of S i c h u a nU n i v e r s i t y ,C h e ng d u ,610041,Chi n a ʌA b s t r a c t ɔ O b je c t i v e T o e x p l o r e t h e d e v e l o p m e n t p a t t e r nof n e w l y e m e rg i n g m a j o r i n f e c t i o u s d i s e a s e s ,t o p r e d i c t th e t r e n do f c h a n g e si nh o s p i t a l i z e d p a t i e n t s ,a n d t o p r o v i d e s c i e n t i f i c b a s i s f o r r e s p o n d i n g t o p u b l i c h e a l t he m e r ge n -c i e s ,a s s e s s i n g m e d i c a l m a n p o w e rn e e d s ,a n df o r m u l a t i ng e p i d e m i c p r e v e n t i o na n dc o n t r o ls t r a t e gi e si nt h ef u -t u r e .M e t h o d s B a s e do n t h e t h e o r y o f t h eS E I R m o d e l (s u s t a i n a b l e e x po s e da f f e c t e da n dr e m o v e d ,S E I R ),c o m b i n e d w i t h t h e p r e v e n t i o na n d c o n t r o l p o l i c i e s o fC O V I D -19i nS i c h u a n p r o v i n c e ,ad yn a m i cm o d e l o f i n f e c t i o u s d i s e a s e s i n t h r e es t a g e s o f e a r l y w a r n i n g ,o u t b r e a k a n d r e c o v e r y i n t h e p r o c e s s o f e pi d e m i c t r a n s m i s s i o n w a s e s t a b -l i s h e d .A c c o r d i n g t o t h e r e a l -t i m ed a t ao fC O V I D -19r e l e a s e db y S i c h u a n H e a l t hC o m m i s s i o n ,t h ed a i l y n e w l y co n -f i r m e d c a s e s ,c u m u l a t i v e c o n f i r m e d c a s e s ,d a i l y e x i s t i n g s u s p e c t e d c a s e s ,c u m u l a t i v e d i s c h a r ge d c a s e s a n dd e a t h c a s e s o fC O V I D -19p a t i e n t sf r o mJ a n u a r y 21,2020t oM a r c h25,2020w e r e s e l e c t e d ,a n d t h e l e a s t s q u a r e s o pt i m i z a t i o n a l -g o r i t h m w a su s e d t o s o l v e t h em o d e l p a r a m e t e r s ,o u t p u t t h em o d e l f i t t i n g r e s u l t s ,a n de v a l u a t e t h e f e a s i b i l i t y of t h e m o d e l .R e s u l t s T h eo v e r a l lt r e n do ft h e m o d e l f i t t i ng c u r v e w a sb a s i c a l l y c o n s i s t e n t w i t hth ea c t u a lr e f e r e n c e c u r v e .T h e a v e r a g e a b s o l u t e p e r c e n t a g e e r r o r d u ri n g t h e e a r l y w a r n i n g s t a g ew a s 30.06%,a n d t h e r o o tm e a n s q u a r e e r r o rw a s 17.8404.T h e a v e r a g e a b s o l u t e p e r c e n t a g e e r r o r d u r i n g t h e o u t b r e a k s t a g ew a s 10.14%,a n d t h e r o o tm e a n s q u a r e e r r o rw a s 66.8452.T h e r o o tm e a ns q u a r ee r r o rd u r i n g t h e r e c o v e r yph a s ew a s16.5082.C o n c l u s i o n T h e m u l t i -s t a g eS E I R m o d e l e s t a b l i s h e d i n t h i s a r t i c l eh a s a g o o do v e r a l l f i t t i n g ef f e c t ,w h i c hc a nb eu s e d t o p r e d i c t t h e t r e n do f c h a ng e s i n th en u m b e r o f n e w l y di a g n o s e dm aj o r i n f e c t i o u s d i s e a s e i n p a t i e n t s .ʌK e y wo r d s ɔ E m e r g i n g i n f e c t i o u s d i s e a s e s ; D y n a m i cm o d e l o f i n f e c t i o u s d i s e a s e s ; I n p a t i e n t ; C O V I D -19 2003年世界卫生组织将新发传染病(e m e r g i n gi n f e c t i o u s d i s e a s e s ,E I D )定义为: 由新种或新型病原微生物引起的传染病,以及近年来导致地区性或国际性公共卫生问题的传染病[1]㊂与以往传染病相比,新发传染病不仅具有传染病的基本特征,还具有突发性㊁不确定性和难以预测等特点,是所有传染病中最有威胁性㊁危害性和破坏性的疾病[2]㊂自1972年以来,全球已发现新发传染病约40余种,且仍以每年新发1种的态势不断增长,是全球公认的重大公共卫生难题之一[3]㊂2019年底,一种新型冠状病毒(c o r o n a v i r u sd i s e a s e2019,C O V I D -19)在人群中传播开来,并在极短时间内迅速席卷全球多个国家和地区,形成世界范围内大流行,其影响范围远超2003年的非典疫情,对人类的生命安全造成了严重危害[4]㊂疫情暴发之后,众多学者采用不同332中国社会医学杂志2024年4月第41卷第2期 C h i n e s e J o u r n a l o f S o c i a lM e d i c i n e ,A pr i l 2024,V o l .41,N o .2数学模型对其进行预测分析,但由于不同干预措施改变了疾病的自然传播规律,给模型构建和预测带来了严峻的挑战[5-7]㊂2020年1月21日,四川省报道首例输入性新冠病毒感染确诊病例,随后在多个地区相继爆发㊂1月24日四川省启动突发公共卫生事件Ⅰ级响应,并采取严格的联防联控措施㊂考虑到新冠病毒感染患者存在潜伏期且具有传染性,对疾病的传播有着巨大影响㊂因此,本文基于经典的S E I R传染病动力学模型,结合四川省不同阶段防控措施,分析隔离住院人数变化,为评估疫情发展趋势及防控策略提供依据㊂1资料与方法1.1数据来源与收集新冠病毒感染患者数据来自四川省卫生健康委员会官方网站,人口学数据来自‘四川省统计年鉴(2020)“㊂按照国务院发布关于‘新冠肺炎疫情风险区划定及管控方案“中风险区域解除标准,匹配四川省启动重大突发公共卫生事件时间节点,选取2020年1月21-3月25日新冠疫情统计结果进行建模分析,共计65天㊂1.2建立模型假设①忽略人口的迁入㊁迁出㊁出生㊁死亡以及境外输入等因素,即总人口数恒定不变;②疑似患者与确诊患者具有相同的传染能力,且不存在无症状感染者;③被诊断出的疑似患者和确诊患者均被完全隔离,不再具有传染性;④患者康复后携带相应抗体,且不会发生二次感染㊂1.3确定模型结构已有研究表明,新冠病毒感染患者不仅存在潜伏期,还有较强的病毒传播能力[8-10]㊂因此,本文考虑潜伏期患者的传染性,结合四川省防疫政策,如停工停学㊁限制出行㊁区域管控㊁早期筛查㊁追踪隔离和集中救治等,将人群分为6类,建立多阶段S E I R模型㊂其中仓室S表示易感染者,仓室E表示潜伏期患者,仓室E q表示隔离的潜伏期患者,仓室I表示感染者,仓室H表示住院患者,仓室R表示康复患者㊂见图1㊂图1多阶段S E I R模型结构流程图1.4构建微分方程本文将四川省2020年新冠病毒病毒感染的疫情传播时间划分为三个阶段㊂第一阶段指发现第一例病例至启动突发公共卫生事件Ⅰ级响应,称预警阶段 ;第二阶段指启动突发公共卫生事件Ⅰ级响应至Ⅱ级响应,称 暴发阶段 ;第三阶段指启动突发公共卫生事件Ⅱ级响应至Ⅲ级响应,称 恢复阶段 ㊂同时将停工停学㊁限制出行和区域管控等封锁措施看成对传染因子β的控制,将早期筛查㊁追踪隔离和集中救治等检疫措施看成对潜伏期患者漏检率δ的控制㊂考虑到四川省防控措施是分阶段实施,所以将β和δ设为关于时间的阶梯函数㊂由此得到:β(t)=β,tɤτ1k1β,τ1<tɤτ2k1β,t>τ2(1)β(t)=δ,tɤτ1k1δ,τ1<tɤτ2k1δ,t>τ2(2)其中k1㊁k2是传染因子β的控制参数㊂在预警阶段,k1=k2=1;在暴发阶段,0<k1ɤ1;在恢复阶段,0<k2ɤk1ɤ1㊂k3㊁k4是潜伏期患者漏检率δ的控制参数㊂在预警阶段,k3=k4=1;在暴发阶段,0<k3ɤ1;在恢复阶段,0<k4ɤk3ɤ1㊂τ1是启动突发公共卫生事件Ⅰ级响应的开始时间,τ2是启动突发公共卫生事件Ⅱ级响应的开始时间㊂由此可得3个阶段综合控制的微分方程:d S(t)d t=β(t)[E(t)+I(t)]S(t)Nd E(t)d t=β(t)[E(t)+I(t)]S(t)N-(1-q)σE(t)-q E(t)d E q(t)d t=q E(t)-αE q(t)d I(t)d t=(1-q)δ(t)σE(t)-γI(t)d H(t)d t=(1-q)(1-δ(t))σE(t)+σE q(t)-γH H(t)d R(t)d t=γI(t)+γH H(t)(3)其中S(t)㊁E(t)㊁E q(t)㊁I(t)㊁H(t)㊁R(t)㊁β(t)㊁δ(t)分别表示t时刻易感染者数量㊁潜伏期患者数量㊁隔离潜伏期患者数量㊁感染者数量㊁住院患者数量㊁康复患者数量,传染因子和潜伏期患者的漏检率㊂q表示潜伏期患者的隔离率,α表示隔离潜伏期432中国社会医学杂志2024年4月第41卷第2期 C h i n e s e J o u r n a l o f S o c i a lM e d i c i n e,A p r i l2024,V o l.41,N o.2患者的确诊速率;﹯为潜伏期的倒数,表示潜伏期患者向感染者的转化速率;㻐I 为感染期的倒数,表示未隔离感染者的恢复速率;㻐H 表示住院患者的恢复速率,N 表示总人口数㊂1.5 求解模型参数模型中仓室S ㊁E q ㊁R ㊁H 的初始值选自四川省官方公布的疫情数据和统计指标㊂仓室I 和仓室E 的初始值因尚无准确数据,故通过基本再生数R 0进行测算估计㊂见表1㊂基本再生数R 0指在没有任何干预措施的前提下,一个全是易感染者构成的群体中,一个感染者在其平均患病期内所传染的人数[11]㊂若R 0>1,表示疾病即将暴发;若R 0=1,表示疾病发展不随时间变化;若R 0<1,表示疾病走向消亡㊂根据S E I R 模型理论,早期自由传播的感染人数与总人口相比可忽略不计,故当t 趋近于0时,S (t)趋近于N ,此时基本再生数R 0表示为:R 0=(1+λγ1)(1+λγ2)(4)其中λ=l n Y (t )/t 表示早期指数增长时的增长率,Y (t)是截至到t 时刻有症状的感染人数㊂潜伏期表示为T E =1/γ1,感染期表示为T I =1/γ2㊂参数﹯和㻐I 的估计值参考新冠患者潜伏期和感染期的相关研究报道,而其余参数则采用最小二乘优化问题算法进行求解获得[12]㊂见表2㊂表1 模型仓室初始值设定参数含义取值说明数值S (0)易感染者的初始值2019年末四川省总人口数83750000E (0)潜伏期患者的初始值基于R 0测算估计162E q (0)隔离潜伏期患者的初始值官方数据0I (0)感染者的初始值基于R 0测算估计39H (0)住院患者的初始值官方数据(确诊患者+疑似患者)6R (0)康复患者的初始值官方数据0表2 模型参数估计值设定参数含义取值说明数值β传染因子算法求解0.7281δ潜伏期患者的漏检率算法求解0.8285q 潜伏期患者的隔离率算法求解0.6464α隔离潜伏期患者的确诊速率算法求解0.3863σ潜伏期患者向感染者的转化速率文献报道[13]1/5.1γI 感染者的恢复速率文献报道[14]1/7㻐H住院患者的恢复速率算法求解0.1126k 1β暴发阶段的控制参数算法求解0.7228k 2β恢复阶段的控制参数算法求解0.0014k 3δ暴发阶段的控制参数算法求解0.0012k 4δ恢复阶段的控制参数算法求解0.00121.6 模型拟合结果本文运用M a t l a b2016a 分析软件,采取四阶R u n ge -K u t t a 算法,求解模型微分方程,输出模型数值解,并与参考值H (t)进行校正检验㊂具体公式如下:y i +1=yi h 6(K 1+2K 2+2K 3+K 4)K 1=f (x i ,y i )K 2=f (x i +h 6,yi +h 6K 1)K 3=f (x i +h 6,yi +h 6K 2)K 4=f (x i +h 6,yi +h6h K 3)(5)1.7 模型效果评价本文选择平均绝对百分比误差(m e a na b s o l u t ep e r c e n t a ge e r r o r ,MA P E )和均方根误差(r o o tm e a n s qu a r e de r r o r ,R M S E )对模型拟合效果进行评价㊂MA P E 表示预测值与真实值的偏差程度,R M S E 表示预测值与真实值的离散程度,两者取值越小,表明模型拟合效果越好㊂具体公式如下:2 结果2.1 疫情传播发展概况四川省各市(自治州)均存在确诊病例,其中本土病例539例,境外输入病例6例,共累计报告545例㊂2020年1月21日发现首例确诊病例,2020年1月30日新增确诊病例最多,为36例,2020年3月5日再无新增确诊本土病例㊂见图2㊂2.2 疫情传播防控效率传染因子β和潜伏期患者漏检率δ均呈下降趋势㊂其中β在恢复阶段下降程度最为显著,由0.5263降至0.0010,下降率为72.15%;δ在暴发阶段下降程度最为显著,由0.8285降至0.0010,下降率为99.88%㊂见图3㊂532中国社会医学杂志2024年4月第41卷第2期 C h i n e s e J o u r n a l o f S o c i a lM e d i c i n e ,A pr i l 2024,V o l .41,N o .2图2四川省每日新增确诊病例和累计确诊病例变化情况图3 传染因子β和潜伏期患者漏检率δ不同传播阶段变化情况2.3 疫情传播住院人数模型拟合曲线与实际参考曲线的变化情况基本一致,均呈先上升后下降的发展趋势㊂在2020年2月10日实际住院患者数量最多,为809例;在2020年2月7日预测住院患者数量最多,为723例㊂见图4㊂图4 四川省每日新冠住院患者实际情况与拟合结果2.4 模型拟合效果预警阶段M A P E 为30.06%,R M S E 为17.8404;暴发阶段MA P E 为10.14%,R M S E 为66.8452,恢复阶段R M S E 为16.5082㊂其中暴发阶段MA P E 最小,表明拟合准确度最高,恢复阶段R M S E 最小,表明拟合稳定性最好㊂3 讨论3.1 疫情发展防控评估自2020年1月21日报告首例确诊病例后,四川省卫生部门通过启动重大突发公共卫生事件响应,在切断传播途径和隔离传染源两个方面采取多632中国社会医学杂志2024年4月第41卷第2期 C h i n e s e J o u r n a l o f S o c i a lM e d i c i n e ,A pr i l 2024,V o l .41,N o .2种控制措施㊂由研究结果可以看出,传染因子β和潜伏期患者漏检率δ在暴发阶段均出现明显降低,仅39天就实现了确诊病例的零增长,充分表明了防疫措施实施的科学性和有效性,这也与国内外众多学者的研究结果相一致㊂如曹盛力等[15]基于潜伏期传播能力和隔离干预措施的考虑构建了修正S E I R模型,得出利于防控决策的相关结论;T a n g 等[16]基于实际传播情况建立S S q E E q I A H R模型,发现隔离和接触者追踪两种控制措施均可有效减少疫情的传播㊂3.2住院患者变化情况在预警阶段,住院患者表现为缓慢上升㊂这是因为在疫情传播的初期阶段,由于新冠病毒感染具有突发性和不确定性等特点,致使卫生部门未能及时采取有效的防控措施,因此病毒在人群中自由传播,仅依靠患者自主就医的方式进行诊断隔离㊂在暴发阶段,住院患者呈现先快速上升趋势,随后开始缓慢下降㊂其原因可能是此时正值我国春节期间,省内各地区大范围的跨区返乡㊁走访亲朋和集会聚餐等人群流动,再加上人们早期缺乏对疾病的防范意识,从而加剧了疾病的快速传播㊂但随后政府部门立即启动公共卫生事件I级响应,采取全面联防联控政策,严格筛查易感人群,并加强全民防范教育等,从根本上控制了疾病的传播速度㊂在恢复阶段,住院患者呈快速降低直至归零㊂原因在于暴发阶段实施的联防联控政策,致使多数传染性病例被完全隔离,疾病的传播风险得到了完全控制,表明疫情防控已取得了阶段性胜利㊂3.3模型拟合效果评价在预警阶段,对仓室E和仓室I进行初始值估算时,是假定所有确诊病例全部刚好在一个潜伏期后被诊断发现为前提,但考虑到疫情初期对病例筛查存在一定滞后,仓室E和仓室I的初始值要远大于估计值,所以拟合值整体小于参考值㊂同时该阶段样本量较少,对误差的敏感性较高,导致模型拟合效果较为一般㊂在暴发阶段,通过对参数β和δ进行范围限制,优化求解算法,防止参数过渡拟合,减少误差产生,使得拟合值与参考值基本相同㊂但此时R M S E数值出现大幅度提高,说明拟合值与参考值之间存在较大的波动,提示有离群值的存在,致使模型拟合稳定性较差㊂在恢复阶段,由于疑似病例解除嫌疑后可以立即出院,而确诊病例需在发病症状解除后,至少满足一个潜伏期后不再发病方可出院,所以疑似病例的隔离解除速率远大于确诊病例㊂而本文在求解过程中,是将两者的隔离解除速率设为相等,故得到的拟合值全部大于参考值,但此阶段的R M S E最小,说明拟合值与参考值之间离散趋势较为稳定,表明模型拟合效果较好㊂3.4研究结论与局限性本文建立的多阶段S E I R模型能够有效地将多种防疫措施和疾病发展规律相结合,精准预测新发传染病住院患者人数的变化规律,表明该模型理论具有应用的可行性,也为医院应急医疗需求和医疗资源分配提供可靠依据㊂但本研究仍存在不足之处,例如:①未考虑人口流动㊁无症状感染者和康复患者的二次感染;②未考虑潜伏期患者与确诊患者传染能力是否存在差别;③未考虑隔离比例q是否会随防疫政策调整有所改变㊂因此,在后续研究中,需考虑人口流动和时滞因素所造成的影响,修正模型的具体参数,并优化求解算法,从而精准地描述疾病的发展规律,建立完善的传染病动力学模型,为疫情防控策略的制定提供理论依据㊂参考文献[1]阮冰.我国新发传染病的流行现况[J].临床内科杂志,2016,33(2):81-84.[2]刘庄.新发传染病[J].中国临床医生,2006,34(3):6-8.[3]明平静,刘胜军,刘涛.新发传染病带给疾病预防控制工作的思考[J].解放军预防医学杂志,2017,35(1):82-84.[4]李盈科,赵时,楼一均,等.新型冠状病毒肺炎的流行病学参数与模型[J].物理学报,2020,69(9):15-24.[5] O s t h u sD,H i c k m a n nKS,C a r a g e aPC,e t a l.F o r e c a s-t i n g s e a s o n a l i n f l u e n z aw i t has t a t e-s p a c eS I R m o d e l[J].A n nA p p l S t a t,2017,11(1):202-224. [6]王小莉,曹志冬,曾大军,等.应用S E I R模型预测2009年甲型H1N1流感流行趋势[J].国际病毒学杂志,2011,18(6):161-165.[7]张天琛,曾志笠,李中坚,等.江西省新型冠状病毒肺炎疫情防控效果评估:基于多阶段S E I R模型的研究[J].现代预防医学,2021,48(2):339-344. [8] R o t h eC,S c h u n k M,S o t h m a n nP,e t a l.T r a n s m i s s i o no f2019-n C o Vi n f e c t i o n f r o ma n a s y m p t o m a t i c c o n t a c ti n G e r m a n y[J].N E n g lJ M e d,2020,382(10):970-971.[9]杨孝坤,李昱,赵宏婷,等.新型冠状病毒感染不同阶段的传染性研究进展[J].中华流行病学杂志,2021,42(1):33-38.[10]桑茂盛,丁一,包铭磊,等.基于新冠病毒特征及防控措施的传播动力学模型[J].系统工程理论与实践,2021,41(1):124-133.[11]耿辉,徐安定,王晓艳,等.基于S E I R模型分析相关干预措施在新型冠状病毒肺炎疫情中的作用[J].暨南大学学报(自然科学与医学版),2020,41(2):175-180. [12]王霞,唐三一,陈勇,等.新型冠状病毒肺炎疫情下武汉及周边地区何时复工?数据驱动的网络模型分析[J].中国科学(数学),2020,50(7):969-978. [13] L a u e rS A,G r a n t zK H,B iQ,e ta l.T h e i n c u b a t i o np e r i o do fc o r o n a v i r u sd i s e a s e2019(C O V I D-19)f r o mp u b l i c l y r e p o r t e dc o n f i r m e dc a s e s:e s t i m a t i o na n da p-p l i c a t i o n[J].A n n I n t e r n M e d,2020,172(9):577-582.[14] T oK K,T s a n g OT,L e u n g W S,e t a l.T e m p o r a l p r o-f i l e so fv i r a ll o a di n p o s t e r i o ro r o p h a r y ng e a ls a l i v as a m p l e sa n ds e r u m a n t i b o d y r e s p o n s e sd u r i n g i n f e c-t i o nb y S A R S-C o V-2:a no b s e r v a t i o n a lc o h o r ts t u d y[J].L a n c e t I n f e c tD i s,2020,20(5):565-574. [15]曹盛力,冯沛华,时朋朋.修正S E I R传染病动力学模型应用于湖北省2019冠状病毒病(C O V I D-19)疫情预测和评估[J].浙江大学学报(医学版),2020,49(2):178-184.[16] T a n g B,W a n g X,L iQ,e t a l.E s t i m a t i o no f t h e t r a n s-m i s s i o n r i s ko f t h e2019-n C o Va n d i t s i m p l i c a t i o n f o rp u b l i ch e a l t hi n t e r v e n t i o n s[J].J C l i n M e d,2020,9(2):462.(收稿时间2023-06-07)(本文编辑熊月琳)732中国社会医学杂志2024年4月第41卷第2期 C h i n e s e J o u r n a l o f S o c i a lM e d i c i n e,A p r i l2024,V o l.41,N o.2。

机器学习PAI⽤⼾指南·法律声明法律声明阿⾥云提醒您在阅读或使⽤本⽂档之前仔细阅读、充分理解本法律声明各条款的内容。

如果您阅读或使⽤本⽂档，您的阅读或使⽤⾏为将被视为对本声明全部内容的认可。

1. 您应当通过阿⾥云⽹站或阿⾥云提供的其他授权通道下载、获取本⽂档，且仅能⽤于⾃⾝的合法合规的业务活动。

本⽂档的内容视为阿⾥云的保密信息，您应当严格遵守保密义务；未经阿⾥云事先书⾯同意，您不得向任何第三⽅披露本⼿册内容或提供给任何第三⽅使⽤。

2. 未经阿⾥云事先书⾯许可，任何单位、公司或个⼈不得擅⾃摘抄、翻译、复制本⽂档内容的部分或全部，不得以任何⽅式或途径进⾏传播和宣传。

3. 由于产品版本升级、调整或其他原因，本⽂档内容有可能变更。

阿⾥云保留在没有任何通知或者提⽰下对本⽂档的内容进⾏修改的权利，并在阿⾥云授权通道中不时发布更新后的⽤⼾⽂档。

您应当实时关注⽤⼾⽂档的版本变更并通过阿⾥云授权渠道下载、获取最新版的⽤⼾⽂档。

4. 本⽂档仅作为⽤⼾使⽤阿⾥云产品及服务的参考性指引，阿⾥云以产品及服务的“现状”、“有缺陷”和“当前功能”的状态提供本⽂档。

阿⾥云在现有技术的基础上尽最⼤努⼒提供相应的介绍及操作指引，但阿⾥云在此明确声明对本⽂档内容的准确性、完整性、适⽤性、可靠性等不作任何明⽰或暗⽰的保证。

任何单位、公司或个⼈因为下载、使⽤或信赖本⽂档⽽发⽣任何差错或经济损失的，阿⾥云不承担任何法律责任。

在任何情况下，阿⾥云均不对任何间接性、后果性、惩戒性、偶然性、特殊性或刑罚性的损害，包括⽤⼾使⽤或信赖本⽂档⽽遭受的利润损失，承担责任（即使阿⾥云已被告知该等损失的可能性）。

5. 阿⾥云⽹站上所有内容，包括但不限于著作、产品、图⽚、档案、资讯、资料、⽹站架构、⽹站画⾯的安排、⽹⻚设计，均由阿⾥云和/或其关联公司依法拥有其知识产权，包括但不限于商标权、专利权、著作权、商业秘密等。

⾮经阿⾥云和/或其关联公司书⾯同意，任何⼈不得擅⾃使⽤、修改、复制、公开传播、改变、散布、发⾏或公开发表阿⾥云⽹站、产品程序或内容。

基于LFM算法的改进社区发现算法肖永嘉;朱征宇【摘要】由于能够反映网络内部结构,重叠社区划分在各领域有着越来越重要的作用.LFM算法是其中较为流行的一种社区划分方法.但其存在一些缺点,例如在网络变得庞大和复杂的时候,时间消耗会变得巨大.为了解决这一问题,提出核心区域的概念,并藉此对LMF算法进行改进.最后通过实验验证,发现该算法能够减小时间消耗,同时能够得到更为可靠的社区划分.【期刊名称】《现代计算机（专业版）》【年(卷),期】2017(000)014【总页数】6页(P21-25,48)【关键词】重叠社区划分;LFM;核心区域【作者】肖永嘉;朱征宇【作者单位】重庆大学计算机学院,重庆 400000;重庆大学计算机学院,重庆400000【正文语种】中文由于能够反映网络内部结构，重叠社区划分在各领域有着越来越重要的作用。

LFM算法是其中较为流行的一种社区划分方法。

但其存在一些缺点，例如在网络变得庞大和复杂的时候，时间消耗会变得巨大。

为了解决这一问题，提出核心区域的概念，并藉此对LMF算法进行改进。

最后通过实验验证，发现该算法能够减小时间消耗，同时能够得到更为可靠的社区划分。

重叠社区划分；LFM；核心区域现实世界的很多复杂的相互作用的系统往往被抽象成网络来表示，用来让人们更好地理解复杂系统的全部特性，更好地应对现实的变化。

例如互联网环境下的社交网络、电子商务；流行病传播学中的疾病预防控制过程，生物学网络中蛋白质组织构造等。

随着人们对复杂网络的研究日益深入，社区结构作为复杂网络存在的普遍特征，由于能有效地揭示网络系统中群体的共性规律，是解决复杂系统的基础，又能推进相关应用的发展，已经成为网络研究的一个重要分支。

而重叠社区的发现可以更为准确地理解网络内部的拓扑结构信息，在近些年的研究中得到了越来越多的关注。

社区并没有一个严格意义上的定义，较为广泛接受的是Newman和Gievan提出的“同一社区内的点与点之间的链接更紧密，不同社区之间的点的链接更稀疏[1，2]。

复杂⽹络中聚类算法总结⽹络，数学上称为图，最早研究始于1736年欧拉的哥尼斯堡七桥问题，但是之后关于图的研究发展缓慢，直到1936年，才有了第⼀本关于图论研究的著作。

20世纪60年代，两位匈⽛利数学家Erdos和Renyi建⽴了随机图理论，被公认为是在数学上开创了复杂⽹络理论的系统性研究。

之后的40年⾥，⼈们⼀直讲随机图理论作为复杂⽹络研究的基本理论。

然⽽，绝⼤多数的实际⽹络并不是完全随机的。

1998年，Watts及其导师Strogatz在Nature上的⽂章《Collective Dynamics of Small-world Networks》揭⽰了复杂⽹络的⼩世界性质。

随后，1999年，Barabasi及其博⼠⽣Albert在Science上的⽂章《Emergence of Scaling in Random Networks》⼜揭⽰了复杂⽹络的⽆标度性质(度分布为幂律分布)，从此开启了复杂⽹络研究的新纪元。

随着研究的深⼊，越来越多关于复杂⽹络的性质被发掘出来，其中很重要的⼀项研究是2002年Girvan和Newman在PNAS上的⼀篇⽂章《Community structure in social and biological networks》，指出复杂⽹络中普遍存在着聚类特性，每⼀个类称之为⼀个社团(community)，并提出了⼀个发现这些社团的算法。

从此，热门对复杂⽹络中的社团发现问题进⾏了⼤量研究，产⽣了⼤量的算法，本⽂试图简单整理⼀下复杂⽹络中聚类算法，希望对希望快速了解这⼀部分的⼈有所帮助。

本⽂中所谓的社团跟通常我们将的聚类算法中类(cluster)的概念是⼀致的。

0. 预备知识为了本⽂的完整性，我们⾸先给出⼀些基本概念。

⼀个图通常表⽰为G=(V,E)，其中V表⽰点集合，E表⽰边集合，通常我们⽤n表⽰图的节点数，m表⽰边数。

⼀个图中，与⼀个点的相关联的边的数量称为该点的度。

一种快速检测重叠社区的方法王一萍【摘要】在分析现实世界网络时,发现功能类似个体的自然群体是一个关键任务.在社会和生物网络中社区间的重叠是常见的,事实上,社区间的重叠密度比社区内非重叠区域重叠密度要大.现大多数检测重叠社区算法假设社区比周围区域密集,错误地将重叠部分识别为社区.而这些算法大多计算量大,不能合理地随网络大小而改变.提出了快速搜索重叠社区算法(fast search overlapping communityalgorithm,FSOCA),一种基于局部连接考虑的重叠社区识别算法.实验结果表明,FSOCA在计算时间上优于一些流行的重叠社区检测算法,且不影响质量.【期刊名称】《高师理科学刊》【年(卷),期】2018(038)007【总页数】5页(P28-31,36)【关键词】重叠社区;社会网络;局部连接;复杂网络【作者】王一萍【作者单位】齐齐哈尔大学计算机与控制工程学院,黑龙江齐齐哈尔 161006【正文语种】中文【中图分类】TP313社会网络由有限个体及它们之间链接组成．一个连接基于他们共同的兴趣、工作或犯罪伙伴关系等联系起来，这种联系出现或消失复杂性形成有意义拓扑结构．同时，网络通常是巨大的，从而阻止了应用大多数图理论算法．分析社会网络意图是新颖和可伸缩计算帮助下对大型复杂网络产生有用见解．在一社会系统中，个体倾向于与其志同道合人或交往更频繁人形成小组，比与其他人密切，导致社区形成．社区中成员是紧密相连，属于不同社区成员间交互少．此外，不同领域有共同兴趣和目的人形成重叠社区．社区的识别有许多实际应用，如电信服务提供商会采取措施留住特定社区内有重要联系的消费者．商业网站可通过增加某些社区内销售提供市场，通过小部分有影响力人，可很容易将一个信息进行传播．事实上，可以很容易做到局部发布信息传播到大量人群中，如政治观点信息、自然灾害及新媒体等通过社交网络迅速传播．网络通常由数百万节点和数十亿边组成，需快速而高效方法从大规模网络中挖掘有用信息，需要考虑到节点局部信息，算法除快速还要克服内存的限制．本文提出了基于局部连接分数计算的大型网络重叠社区搜索算法，该方法已应用于多个大型社会网络和生物网络中．将被检测到的社区与各对应网络社区进行了比较，并与一些流行重叠社区检测算法相比，FSOCA在时间和效率方面表现都良好．社区检测的问题是识别出自然存在的群体，群体中节点连接紧密，不同组节点连接稀疏．社会团体从拓扑角度说是图群，而一般说，图聚类只适用于比社会网络小的网络．图聚类是优化问题，在计算上难以解决．社会网络要求有更快的算法在大网络上能够很好地使用．文献[1]中有许多图聚类方法，探索边划分社区．另外，局部优化法通过优化描述局部拓扑结构参数的适应度函数来实现最优解．将社区检测简化为局部优化更有说服力．如已提出的定义局部适应度分数[2]，是指位于社区内节点邻接点分数．标签传播算法（LPA），而COPRA[3]修改LPA，以找到重叠社区．在SLPA中，当发送节点发送最多可能的标签时，这种方法可帮助一个节点根据收到标签概率信息决定它在每个社区强度．尽管提到的方法简单且很快，但大多是发现非重叠集群的[4]．发现重叠集群算法主要是计算上的限制，使算法不适用于大型真实网络．FSOCA是一种快速进化算法，在一些局部计算分数基础上发现重叠社区，在规模超大的社交网络扩展很好．通过增加选择多个接近社区，不仅是最好社区，而且也节省迭代．此外，该方法检测到的社区不局限于层次结构，结果不依赖节点的顺序．给定一个无向未加权图，社区检测问题是找到子图集，对于中任意节点在中比与其他有更多连接．是集合中不含节点的子图，每个是一社区．对于每个节点，和的定义其中：是含的社区集；是不含社区集．如每个恰属一个社区，则为分离社区，否则称重叠社区．本文提出了在给定图中发现重叠集群OCFS算法．每个节点与中任何社区比与任何社区有更好连接，因此，需确定与中所有社区都有很好连接，这是FSOCA工作原理．设是节点邻接点集，描述为设是在社区中邻接点（），即与节点在同一社区邻接点集合，描述为FSOCA定义关于一个节点与它所在社区的连接度．因此如一个顶点与社区中大多数节点连接，它就被认为其在社区内连通性很好．对每个节点所属每个社区对应一个社区连通性得分为确保一个节点在任何社区中至少有个邻接点，修改式（5）得社区联系得分如值非常大，那么会忽略小而密集社区；如值非常小则会发现稀疏大社区．结果表明，该算法对低值不敏感，且对= 2大小不同网络有较好一致性．算法还为每个节点关于它所在的社区定义了邻接点连通性得分，是对在社区中节点邻接点个数与所有邻接点之比此分数强调节点邻接点出现在社区中比例．须指出社区连通性分数决定了节点对其社区的归属，而邻接点连通性得分只定义节点加入新节点的兴趣社区．FSOCA的原则是社区由个体发起，并受到它们邻接点和邻接社区影响．一个节点吸引其邻近个体成为其社区一部分，那些找到足够连接个体可能会选择留下来．在新添加成员迭代过程之后，社区进一步扩展．2.3.1 初始社区最初每个节点和它至少个邻接点一起构建一个社区．因此，社区数等于度数大于或等于的节点数，这样每个节点都成为由它和它邻接点初始社区的成员，允许初始社区之间重叠．这种方法进一步实现了一个节点可参与多个社区，可以同时选择留在不止一个具有高连接度分值的社区，而离开其他的社区．设初始社区结构表示为，此外，设，被定义为的外围节点集．该算法将迭代２个阶段：离开阶段和扩展阶段．设包含这２个阶段的每个迭代被称为一个stage．另外，在stage 后得到的社区结构被表示为，很重要的是，它始终是任何社区的外围节点，这些节点要在接下来的阶段中要么离开，要么扩展．2.3.2 离开阶段在此阶段，当节点发现它在所在社区中没有足够连接时，将会离开这个社区．每个节点分配分数和，由式（6）、式（7）给出．因此，为每个节点所参与的社区结构中的任何社区，得到社区连通分数列表和邻居连通分数列表．如一个节点社区连通性分值大于一定界限分，它就被认为在对应社区中有足够连通性，称这个界限为保留界限，它是从社区连通性评分列表中计算得到的．本文采用类似于桶的方法，快速确定保留界限．对于所有社区的每一个外围节点，如果它的社区连通分数低于它的保留界限，则离开社区．移走仅有的外围节点才能确保构成一个社区核心的节点永远不会被消除．然而，少于个节点的任何社区都被认为是无关紧要的，并且被清除．对整个社区计算分数及和移走外围节点执行递归，直到没有节点离开任何社区．2.3.3 扩展阶段在离开阶段后，将继续扩展社区到其邻近节点．因此，在每个社区的外围节点集中包括每个相邻节点，如果具有条件：（1）节点还没有包含在社区中；（2）节点对加入这个社区非常感兴趣，则将此节点加入该社区中．加入一个新社区兴趣高是通过高的邻居连通性分数描述的，确保一个节点邻居连通性分数高，分数大于其加入界限．加入的计算是从邻居连通性分数列表，计算方法类似于保留界限的求法．在此之后，将包含的新添加节点，以便在下一阶段进行移走或扩展．一方面，只有外围节点扩展允许重新包含被删除的节点；另一方面，需要注意在社区中不适合的节点不会重复添加，并在离开阶段被删除，它也有助于FSOCA 的收敛．在扩展阶段之后，此阶段所获得社区结构作为输入传递到下一个阶段的离开阶段．如果在某阶段的某些特定社区的所有外围节点在离开阶段被移除，则这些社区在后面阶段不能进一步扩大，但这些社区仍为其节点连接得分列表提供帮助．在一个阶段中，当所有现有的社区中没有外围节点时FSOCA停止．2.3.4 删除重复社区重叠社区的检测算法允许网络中几乎所有节点都成为其他社区的一部分．这是因为每个初始社区都可以扩展加入新节点，而不考虑这些节点是否在其他社区中，所以在每个阶段某些社区可能会发展成为接近重复的社区．接近重复的社区对确定通过相似度量定义在每个阶段都执行删除重复社区，在把社区传递给离开阶段之前，并在每次迭代之后进行．从2种观点来看，重复删除是很重要的：（1）这防止了分数分布不受期望的倾斜；（2）删除了一些接近重复的社区，计算时间也减少了．在FSOCA中，重复删除过程将参数OVL作为输入．在2个社区被识别为接近时，设置OVL为2个社区之间允许的最大重叠阈值，当相似度测量值超过这个阈值时，删除2个社区中较小的．当OVL=1时意味着当2个社区完全相同时消除其中一个．合理的阀值设置为：，本文取OVL=0.6，并试验了不同的OVL值，观察在0.5~0.7范围内的定性条件下输出的稳定性．评估一种社区检测算法的性能可在真实和模拟网络上进行，而模拟网络没有捕捉到与真正网络社区结构相关的重要特征[5-6]．本文只在真实网络上评估FSOCA性能．为验证在大型真实网络上FSOCA性能，在3个大型真实网络上对FSOCA进行评价，网络是无向无权的．Amazon是亚马逊产品联合采购无向网络[7]．产品类别是分层嵌套，对应网络本质上组织为重叠社区结构，在同一层社区产品共享相同功能．DBLP 计算机科学协作网络，如果2名作者一起至少发表一篇论文，他们就会联系在一起．这样网络中成员之间的关系是与研究领域相关的，因此社区高度重叠很自然．Human PPIN人类蛋白质间质是由计算分析部分的结果所收集的PCDq数据集[8-10]，它提供交互网络，也提供复合物（用DBClus进行了实验验证和计算预测）．使用9 268种蛋白质32 198个相互作用网络，人类蛋白复合物数据集含1 078个复合物，构成3 759个蛋白质．只考虑有属于第一类或第二类复合体，这些是经实验验证大量蛋白质复合物．本文采用NMI（标准互信息表）评估划分社区的质量，为评价本文算法，将其与较有名的算法：MOSES，GCE，CORPA，SLPA进行对比．实验结果对比见表1．社会网络是复杂而庞大的，FSOCA通过只选择那些所有都局部连通较好的节点来快速探索社区．在整个算法中计算每个节点的社区连接和邻域连接得分，反映了真实世界的社区属性，这使得该算法适用于大小不等的真实网络．用户可以自由设置任意两个社区之间允许的最大重叠阀值，以及节点应该拥有的最小邻居数量，以确定其在任何社区中的成员．FSOCA的一个局限性是，可以通过该方法检测到的最大社区数量等于网络中节点的数量．而在社会网络中，社区的数量实际上可以是节点数量的２倍．当允许一个节点创建多个社区时，就会发生这种情况，试图在今后的工作中解决这个问题．此外，还希望扩展该方法以使用加权和/或定向网络、动态网络等．【相关文献】[1] Xie J，Kelley S，Szymanski B K．Overlapping community detection in networks：The state-of-the-art and comparative study[J]．ACM Computing Surveys，2013（4）：6521-6540[2] Chen W，Liu Z，Sun X，et al．A game-theoretic framework to identify overlapping communities in social networks[J]．Data Mining and Knowledge Discovery，2010（21）：224-240[3] Ren G，Wang X．Epidemic spreading in time-varying community networks[J]．Chaos An Interdisciplinary Journal of Nonlinear Science，2014，24（2）023116[4] Girvan M，Newman M E．Community structure in social and biologicalnetworks[J]．Proceedings of the national academy of sciences，2002，99（12）：7821-7826[5] 刘世超，朱福喜，甘琳．基于标签传播概率的重叠社区发现算法[J]．计算机学报，2016，39（4）：717-729[6] 周涛，张子柯，陈关荣，等．复杂网络研究的机遇与挑战[J]．电子科技大学学报，2014，43（1）：1-5 [7] Yang J，Leskovec J．Defining and evaluating network communities based on ground-truth[J]．Knowledge and Information Systems， 2015，42（1）：181-213 [8] 张鑫，刘秉权，王晓龙．复杂网络中社区发现方法的研究[J]．计算机工程与应用，2015，51（24）：1-7[9] 李磊，倪林．基于模块度优化的标签传播社区发现算法[J]．计算机系统应用，2016，25（9）：212-215[10] 石梦雨，周勇，邢艳．基于LeaderRank的标签传播社区发现算法[J]．计算机应用，2015，35（2）：448-451。

移动社交网络的重叠社区发现方法洪小龙【摘要】为了解决移动社交网络社区发现不精确的问题,引入移动用户的上下文信息,研究了采用移动用户社交网络的介数来剔除移动社交网络中不稳定的边,利用GN算法快速形成社区核后,采用节点与社区核之间的相似度来获得重叠社区的划分结果.实验结果证明,提出的算法能够提高社区发现的算法精度.【期刊名称】《移动通信》【年(卷),期】2018(042)008【总页数】5页(P33-37)【关键词】GN算法;社区核;时空相似度;重叠社区【作者】洪小龙【作者单位】广州杰赛科技股份有限公司,广东广州 510310【正文语种】中文【中图分类】TP391.41 引言随着移动互联网的快速发展，越来越多的用户通过移动终端可以随时随地与他人进行交流或者购物。

移动运营商越来越关注移动用户“指尖上的消费”的行为倾向[1]，采用社区发现算法来挖掘移动用户的团体结构，为精准营销提供了数据支撑。

社会学的创始人柯晓华[2]认为社会团体的演变能够在一定程度上解释社会现象变化的成因。

因此，移动社区的发现是研究移动社交网络的一个重要任务。

社区发现算法首先用于信息科学、社会科学以及管理科学等领域，并从非重叠社区发现起步，如KL（Kernighan Lin）算法[3]、GN（Given Newman）算法[4]以及快速Newman算法[5]等。

非重叠发现算法得到的社区结构是互相独立的，社区之间不存在交集。

显然，这些算法并不能有效地解释现实社交网络存在的重叠社区现象。

重叠的社区发现算法从实现的机制来说，可以分为两类：基于节点分裂的和基于模块度优化的。

LFM算法[6]是基于模块度优化机制实现的；CPM算法[7]采用完全子图的方法构建重叠矩阵，然后将重叠矩阵变成社区社团邻接矩阵实现重叠社区的划分；CONGA算法[8]是基于节点分裂的机制实现的，该算法是采用传统的GN算法发现非重叠社区，然后通过计算节点之间的介数来决定节点的社团归属。

1互联网+应用n ter n e t A p p lica tio n 电信运营商知识图谱智慧运营管理系统□赵东明田雷刘静石理中国移动通信集团天津有限公司人工智能实验室【摘要】本文打造了"一体两面"的知识图谱运营管理系统，在智能应答和存量运营两大核心业务领域开展了一系列实践，先后完成了智能应答知识图谱，企管支撑知识图谱，权益运营知识图谱，5G换机知识图谱，预离网知识图谱等应用，并打造了面向运营人员的知识图谱个性化管理系统，嵌并嵌入公司运营管理主体流程中形成固化，在存量经营、客户服务、零售运营、预警挽留等多个领域全场景打造A I标杆应用，并验证了 A I赋能业务的价值和规模化应用的可行性。

【关键字】知识图谱系统引言中国移动已进入“客户需求多元化、客户体验个性化、行业特征高度适配化”的数字化运营阶段，商业形态、运营模式相比以往都发生了巨大变化，如何利用大数据、人工智能等新技术，根据通信与数字化服务数据来精准识别客户潜在意图、负面倾向，并发现新商机、避免升级投诉，决定了未来的发展空间与竞争能力。

2020年以来，人工智能领域的发展趋势正在发生重要的变化，由“感知智能”向“认知智能”。

“认知智能”是人工智能技术发展的高级阶段，旨在 赋予机器数据理解、知识表达、逻辑推理、自主学习的能力，使机器能够拥有类似人类的智慧，甚至具备各个行业领域专家的知识积累和运用的能力。

认知智能的实现离不开知识图谱技术、自然语言处理技术的支撑。

知识图谱就是让机器识别人类经验知识的一种很好的表达方法，通过schem a建立数据关系模型来表达客观世界，让机器认识世界，通过在关系模型上建立推理规则来表达人类积累的专业经验，让机器去改造世界。

一、知识图谱运营管理系统天津移动沉淀了多项重要知识图谱模型的通用方法，搭建了完整的知识图谱训练和推理应用架构，打造了构建“一体两面”的知识图谱运营管理体系，在图谱构建、营业推荐、存量保有等领域打造了5大标杆应用，正在持续优化和推广中。

收稿日期：２０１９ ０３ １２；修回日期：２０１９ ０４ ２８ 基金项目：国家重点研发计划资助项目（２０１６ＹＦＢ１０００６００）；中国科学院战略性先导科技专项资肋项目（ＸＤＡ０６０１０３０７）作者简介：刘东江（１９８８ ），男（通信作者），内蒙古人，博士，主要研究方向为数据挖掘、机器学习（ｌｄｏｎｇｊｉａｎｇ＠ｙｅａｈ．ｎｅｔ）；黎建辉（１９７３ ），男，湖北人，研究员，博导，博士，主要研究方向为数据密集型计算、数据密集型存储．基于Ｓｐａｒｋ的并行社区发现算法刘东江１，２，黎建辉１（１．中国科学院计算机网络信息中心，北京１００１９０；２．中国科学院大学，北京１００１９０）摘　要：针对大规模图数据顶点聚类进行研究，提出了一种基于Ｓｐａｒｋ的并行社区发现算法，其在基于极值优化的串行社区发现算法的基础上设计而成。

此外还针对该串行算法在簇调整时因选择顶点数量过少而影响算法运行效率的问题，提出了一种多个顶点选择方法。

该方法会计算一个阈值并发现所有适应度值小于该阈值的顶点，作为被选择的顶点；由于阈值是基于所有顶点的适应度值计算出来的，为了避免非常大的适应度值对阈值造成的影响该方法会限制被选择顶点的数量，若被选择的顶点过多，算法只保留其中的一部分。

同时，还提出了一种顶点过滤方法，其可以有效减少图数据的数据量。

实验表明，提出算法的运行时间明显短于比较的其他基于Ｓｐａｒｋ的并行化社区发现算法，可以发现其运行速度相对较快。

关键词：社区发现；Ｓｐａｒｋ；并行算法；图聚类；图数据中图分类号：ＴＰ３９１ 文献标志码：Ａ 文章编号：１００１ ３６９５（２０２０）０８ ００３ ２２５５ ０６ｄｏｉ：１０．１９７３４／ｊ．ｉｓｓｎ．１００１ ３６９５．２０１９．０３．００５３ＰａｒａｌｌｅｌｉｚｅｄｃｏｍｍｕｎｉｔｙｄｅｔｅｃｔｉｏｎａｌｇｏｒｉｔｈｍｂａｓｅｄｏｎＳｐａｒｋＬｉｕＤｏｎｇｊｉａｎｇ１，２ ，ＬｉＪｉａｎｈｕｉ１（１．ＣｏｍｐｕｔｅｒＮｅｔｗｏｒｋＩｎｆｏｒｍａｔｉｏｎＣｅｎｔｅｒ，ＣｈｉｎｅｓｅＡｃａｄｅｍｙｏｆＳｃｉｅｎｃｅｓ，Ｂｅｉｊｉｎｇ１００１９０，Ｃｈｉｎａ；２．ＵｎｉｖｅｒｓｉｔｙｏｆＣｈｉｎｅｓｅＡｃａｄｅｍｙｏｆＳｃｉ ｅｎｃｅｓ，Ｂｅｉｊｉｎｇ１００１９０，Ｃｈｉｎａ）Ａｂｓｔｒａｃｔ：ＴｈｉｓｐａｐｅｒｆｏｃｕｓｅｄｏｎｇｒａｐｈｃｌｕｓｔｅｒｉｎｇａｎｄｐｒｏｐｏｓｅｄａｐａｒａｌｌｅｌｉｚｅｄｃｏｍｍｕｎｉｔｙｄｅｔｅｃｔｉｏｎａｌｇｏｒｉｔｈｍｂａｓｅｄｏｎＳｐａｒｋ．Ｔｈｉｓａｌｇｏｒｉｔｈｍｗａｓｂａｓｅｄｏｎｓｅｑｕｅｎｃｅｃｏｍｍｕｎｉｔｙｄｅｔｅｃｔｉｏｎａｌｇｏｒｉｔｈｍｕｓｉｎｇｅｘｔｒｅｍａｌｏｐｔｉｍｉｚａｔｉｏｎ．Ｔｈｅｓｅｑｕｅｎｃｅａｌｇｏｒｉｔｈｍｔｒｉｅｄｔｏｃｈｏｏｓｅｏｎｅｖｅｒｔｅｘｅａｃｈｔｉｍｅｗｈｅｎａｄｊｕｓｔｔｈｅｃｌｕｓｔｅｒｓ．Ｓｏｉｔｗｏｕｌｄｔａｋｅｌｏｎｇｔｉｍｅｔｏａｄｊｕｓｔｔｈｅｃｌｕｓｔｅｒｓ．Ｆｏｒｔｈｉｓｒｅａｓｏｎ，ｔｈｅｐｒｏｐｏｓｅｄａｌｇｏｒｉｔｈｍａｄｏｐｔｅｄａｎｅｗｍｕｌｔｉ ｖｅｒｔｉｃｅｓｓｅｌｅｃｔｉｏｎｍｅｔｈｏｄ．Ｔｈｉｓｍｅｔｈｏｄｔｒｉｅｄｔｏｃａｌｃｕｌａｔｅａｔｈｒｅｓｈｏｌｄｖａｌｕｅａｎｄｆｏｕｎｄａｌｌｔｈｅｖｅｒｔｉｃｅｓｗｈｏｓｅｆｉｔｎｅｓｓｖａｌｕｅｗａｓｓｍａｌｌｅｒｔｈａｎｔｈｅｔｈｒｅｓｈｏｌｄｖａｌｕｅ．Ｔｈｅｎｔｈｅｐｒｏｐｏｓｅｄａｌｇｏｒｉｔｈｍａｌｓｏｎｅｅｄｅｄｔｏｃｈａｎｇｅｔｈｅｃａｔｅｇｏｒｙｏｆｔｈｅｓｅｖｅｒｔｉｃｅｓ；ｂｅｓｉｄｅｓ，ａｓｔｈｅｐｒｏｐｏｓｅｄｍｅｔｈｏｄｔｏｋｅｔｈｅｆｉｔｎｅｓｓｖａｌｕｅｓｏｆａｌｌｔｈｅｖｅｒｔｉｃｅｓｉｎｔｏｃｏｎｓｉｄｅｒａｔｉｏｎｗｈｅｎｔｒｉｅｄｔｏｃａｌｃｕｌａｔｅｔｈｅｔｈｒｅｓｈｏｌｄ，ｉｔｎｅｅｄｅｄｔｏｓｅｌｅｃｔｌｉｍｉｔｅｄｎｕｍｂｅｒｏｆｖｅｒｔｉｃｅｓｉｎｏｒｄｅｒｔｏａｖｏｉｄｔｈｅｉｎｆｌｕｅｎｃｅｏｆｅｘｔｒｅｍｅｌｙｌａｒｇｅｆｉｔｎｅｓｓｖａｌｕｅｓ．Ｓｏｉｆｔｈｅｐｒｏｐｏｓｅｄｍｅｔｈｏｄｓｅｌｅｃｔｅｄｇｒｅａｔａｍｏｕｎｔｏｆｖｅｒｔｉｃｅｓ，ｉｔｗｏｕｌｄｏｎｌｙｋｅｅｐｐａｒｔｏｆｔｈｅｍ．Ａｔｔｈｅｓａｍｅｔｉｍｅ，ｔｈｅｐｒｏｐｏｓｅｄａｌｇｏｒｉｔｈｍａｌｓｏａｄｏｐｔｅｄａｎｅｗｖｅｒｔｉｃｅｓｆｉｌｔｅｒｉｎｇｍｅｔｈｏｄ．Ｔｈｉｓｍｅｔｈｏｄｃｏｕｌｄｒｅｄｕｃｅｔｈｅｖｏｌｕｍｅｏｆｇｒａｐｈｄａｔａｅｆｆｉ ｃｉｅｎｔｌｙ．Ｔｈｅｒｅｓｕｌｔｓｓｈｏｗｔｈａｔｐｒｏｐｏｓｅｄａｌｇｏｒｉｔｈｍｔａｋｅｓｓｈｏｒｔｅｒｔｉｍｅｔｈａｎｏｔｈｅｒｐａｒａｌｌｅｌｉｚｅｄａｌｇｏｒｉｔｈｍｓｆｏｒｃｏｍｐａｒｉｓｏｎ．Ｉｔｍｅａｎｓｔｈａｔｔｈｅｐｒｏｐｏｓｅｄａｌｇｏｒｉｔｈｍｒｕｎｓｒｅｌａｔｉｖｅｌｙｆａｓｔｅｒ．Ｋｅｙｗｏｒｄｓ：ｃｏｍｍｕｎｉｔｙｄｅｔｅｃｔｉｏｎ；Ｓｐａｒｋ；ｐａｒａｌｌｅｌｉｚｅｄａｌｇｏｒｉｔｈｍ；ｇｒａｐｈｃｌｕｓｔｅｒｉｎｇ；ｇｒａｐｈｄａｔａ０　引言社区发现算法是图数据挖掘的一个重要组成部分。

复杂网络的重叠社区及社区间的结构洞识别刘世超;朱福喜;冯曦【摘要】大数据环境下如何有效地、准确地识别复杂网络的重叠社区是近年来学者关注的重点。

本文提出一种基于多标签传播方式MLPS（Multiple Label Propagation Strategy）的重叠社区识别算法，该算法首先利用影响力最大化模型选取初始种子集合并赋予它们唯一的标签，然后采用结点间的相似性和影响传播特性共同作用于标签的传播迭代过程，迭代停止后将具有相同标签的结点划分为同一社区。

通过合成网络和真实网络的实验验证了MLPS算法具有较高的准确度和模块度，且具有接近线性的时间复杂度。

另外，在对MLPS算法输出的重叠结构进行分析的基础上，本文提出社区间的结构洞识别算法SHCDA（Structural Holes Between Communities Detection Algorithm），该算法通过分析重叠结构和重叠结点的位置特征，计算重叠结点作为结构洞的得分，最后输出top-k结构洞。

本文在不同特性的数据集上进行实验，结果证明了SHCDA算法具有最好的准确度。

%Many researchers focus on how to detect overlapping communities effectively and accurately when coping with large-scale networks in recent years.This paper proposes a novel overlapping community detection algorithm based on a multiple label propagation strategy,called MLPS algorithm.Firstly,MLPS selects a set of nodes as initial seeds by using In-fluence Maximization Model,each of which is assigned a unique label;Inspired by strategy based on similarity and influence diffusion,MLPS incorporates with these two strategies to guide the process of label propagation;Finally,nodes with the same tag are divided into one community after propagation.Experimental results on synthetic datasetsand real networks illustrate that MLPS has both high accuracy and modularity at the same time.In addition,another algorithm named Structural Holes between Communities Detection Algorithm (SHCDA)is presented on the basis of the output of MLPS.SHCDA computes the scores of overlapping nodes who serve as structural holes by analyzing the overlapping structure and position feature of overlapping nodes,and then selects top-k structural holes as the output.Experimental results on different datasets show that SHCDA gets the best accuracy.【期刊名称】《电子学报》【年(卷),期】2016(044)011【总页数】7页(P2600-2606)【关键词】复杂网络;重叠社区;多标签传播;结构洞识别【作者】刘世超;朱福喜;冯曦【作者单位】武汉大学计算机学院，湖北武汉430072;武汉大学计算机学院，湖北武汉430072;武汉大学计算机学院，湖北武汉430072【正文语种】中文【中图分类】TP391现实世界的许多网络普遍体现了社区结构特性，即同一社区内的结点关系紧密，而不同社区间的结点关系稀疏[1].近年来针对社区发现的算法层出不穷，在社区的层次性和重叠性等方面开展了大量的研究[2～4].本文着重研究社区的重叠性，尤其是大数据环境下，如何有效地解决重叠社区挖掘的问题.社区重叠结点是社区间的桥梁即社区间的结构洞，社区间的结构洞是两个或多个社区之间的非重复关系，占据结构洞的个体拥有更多的机会获取信息或资源[5].识别社区间结构洞的关键在于准确地挖掘网络的重叠结构，从而找出结构洞的候选集合，即社区重叠结点的集合. 一些学者针对结构洞的形成和作用进行建模研究[6,7]，而对结构洞的识别算法还比较少.文献[8]采用拓扑势的方式识别重叠社区和社区间的结构洞，但作者直接将重叠结点作为结构洞，没有定量地分析结构洞的重要性.在实际情况中，我们往往更加关心那些比较重要的结构洞，于是Tang J等[9]提出top-k结构洞挖掘的问题，作者认为结构洞的邻居结点在一定程度上反映该结构洞的重要性，但忽略了对重叠结构的分析.如图1(a)中的结构洞A与图1(b)的结构洞C拥有相同的结构，而图1(b)中的两个社区只存在一个结构洞C，定量计算时C的重要性应大于A.本文的主要贡献：提出一种基于多标签传播方式(MLPS)的重叠社区挖掘算法，算法的输出结果拥有较高的准确度和模块度；分析社区重叠结构，提出社区间的结构洞识别算法(SHCDA)，能有效地挖掘top-k结构洞.Raghavan等[10]提出的标签传播算法LPA(Label Propagation Algorithm)，首次将标签传播应用于社区发现，具有接近线性的时间复杂度.Barber等人[11,12]将标签传播算法转化为优化问题，Xie J[13]结合了路径衰减的思想扩展了对结点邻居的计算，提高了社区划分结果的精度.COPRA(Community Overlap Propagation Algorithm)算法[14]是LPA算法的扩展，可以解决重叠社区挖掘的问题.初始化时每个结点被赋予一组标签对(c,b)，c是标签，b是结点拥有标签c的概率；在标签更新过程中设置阈值v，删除b小于v的标签对.文献[15]指出COPRA算法的阈值应根据结点所处的位置不同而变化，并通过平衡阈值的选择来提高生成社区的质量.SLPA(Speaker-listener Label Propagation Algorithm)[16]通过模拟人类交流的行为特性，定义了动态的交互规则来指导结点的标签更新.文献[17]提出了MLPA(Multi-label Propagation Algorithm)算法，该算法根据结点间的相似性来确定传播概率，具有较高的准确度，但是同COPRA算法一样，算法容易产生大量的社区，导致模块度较低.3.1 算法主要思想COPRA是经典的标签传播算法，在该算法的标签传播过程中，结点直接接受邻居结点的标签，本文定义这种标签传播的方式为DA(Directly Accept)，即其中,Pij表示标签ci从结点i传播到邻居结点j的概率，bi是结点i拥有标签ci的概率.这种直接接受标签的方式并不能真实地反应社会网络中信息和资源的传播，可能会降低算法的准确度.MLPA算法假定两个结点拥有越多的共同邻居，标签在结点间传播的概率就越大，定义这种标签传播的方式为SS(Structural Similarity)，即其中,Sij表示结点i和j的相似性，Γ(i)是结点i的邻居结点集合.在相关工作中[17]已经提到，MLPA算法同COPRA算法一样，容易产生大量的社区，导致输出结果的模块度较低.因此，如何在保证准确度的情况下提高算法的模块度和稳定性，是本文研究的重点.分析现实的网络，结点影响(标签)的传播在一定程度上取决于结点所处的位置，具有较高影响力的结点往往处于社区的核心位置，能够影响周围影响力较低的结点[18].于是，本文定义了一种新的基于影响传播的标签传播方式ID(Influence Diffusion)，即其中,lij为标签从结点i传播到j的度量，φi表示结点i在其邻域结构的相对影响能力，即由式(6)可知结点i的相对影响能力φi取值区间为(0,1]，且φi值越大，结点i的标签传播能力越强.结合式(5)和式(6)可得标签从结点i传播到j的度量lij取值区间为(0,1)，且φi与φj的差值越大，标签越容易传播.由于大部分网络结点的相对影响力有明显的差异，导致标签在网络中不均衡地流动，降低了原有算法的随机性，使得算法能够很快收敛且输出的结果较为稳定.于是本文提出一种基于多标签传播方式(MLPS)的重叠社区识别算法，综合SS和ID两种方式进行标签传播，那么结点i的标签传播到邻居结点j的概率Pij表示为：目前的标签传播算法对网络进行初始化时，为每个结点都赋予一个独立的标签，这会导致输出结果出现大量孤立的小社区，从而降低输出社区的质量.为此，本文采用文献[20]提出的影响力最大化模型，选取网络中一组初始传播结点，使得这些结点能辐射到网络大部分结点，且尽可能的散落在每一个可能的社区，可以减少在传播时不需要的判断开销.另外，COPRA算法的参数v是过滤标签对的阈值，设为全局值是不合理的.本文采用结点依赖的阈值选择方式[15,17]，即任意结点i拥有独立阈值vi.给定结点i的标签对集合为{(c1,b1),(c2,b2),…,(ck,bk)}，定义·p，其中=max{b1,b2,…,bk}，p作为算法的阈值选择参数.这样，既平衡了所有结点的阈值，又能有效地挖掘结构洞.3.2 重叠社区发现的MLPS算法为了提升算法运行的准确性和稳定性，本节提出一种基于多标签传播方式(MLPS)的重叠社区识别算法，算法逻辑流程如图2所示.MLPS算法的迭代停止条件和后处理沿用COPRA算法的设定，因此本文只给出改进的标签传播方式和阈值选择策略的部分代码，即算法1.算法设置两个标签向量：old和new，old.x(new.x)表示结点x更新前(后)的标签，每个结点都拥有一组标签对(c,b)，c是标签，b是结点拥有标签c的概率，N(x)是结点x的邻居集合，算法的唯一参数是阈值选择参数p.3.3 算法的复杂度分析定义N是结点个数，表示平均度，m为结点拥有的平均标签个数，在COPRA算法的基础上，MLPS算法：在初始化时增加了种子集合的选取O(N)；增加了结点间的相似性计算2)和影响传播度量的计算)+O(N·logN)；平衡了阈值后，算法不限制结点拥有的标签数，每次迭代的复杂度·m).算法的迭代次数一般很小，且大部分网络是稀疏的<<N)，当数据量变大时(m<<N)，MLPS算法拥有O(N·logN)的复杂度.在实际计算中，O(N·logN)的复杂度主要是影响力计算造成的.对此，我们可以离线计算所有结点的影响力来提高算法效率.本节根据MLPS算法的输出结果，提出社区间的结构洞识别算法(SHCDA).算法首先将所有重叠结点加入结构洞的候选集合，然后分析社区重叠结构和重叠结点的位置特征，输出重要性得分top-k的结构洞.定义ON为重叠结点集合，Ci是重叠结点i(i∈ON)归属的社区集合，pi,c表示结点i属于社区c的概率，满足pi,c=1.根据文献[9]的分析，结构洞的邻居结点能一定程度地反映其重要性，于是本文将结构洞的邻居结点的加权影响力均值作为该结构洞的重要性得分.那么，结构洞i的重要性得分为：其中,n为结点i的邻居数，Infj表示结点j的重要性；wij=pi,c为结构洞i与其邻居结点j的关系权重，c是结点j归属的社区.本文观测真实的网络数据，发现部分结构洞连接的只是一些普通结点，因受到邻居结点的影响，导致结构洞的得分过低.此外，结构洞所处的结构特性也会影响其重要性得分，令Ci表示重叠结点i归属的社区集合，OCi为结点i所处的重叠结构，即OCi={oc|oc=Ci1∩Ci2∩…∩Cim}其中，Ci={Ci1,Ci2,…,Cim}，m是集合Ci的大小，m=|Ci|且m≥2.然后加入惩罚系数ε来衡量重叠结构的影响，这样算法输出的结果将更加符合真实的情况.根据实验结果，设置ε的经验值为0.1.最终结构洞i的重要性得分计算公式如下：SHCDA算法描述如算法2.一般的，k取值较小，因此时间复杂度近似为O(d·r2)，其中d为重叠结点的平均度，r是重叠结点的个数.在大数据的稀疏网络环境下，d和r都较小，所以算法能够有效地处理大规模网络.5.1 MLPS实验MLPS算法的参数p取值根据数据集的不同而变化.给定数据集D，本文定义p在[0,1]范围内以步长0.05搜索，取使得算法输出结果最优的值作为算法在数据集D 上的参数.5.1.1 评价方法NMI(Normalized Mutual Information)[21]广泛应用于重叠社区挖掘的实验中，NMI值越接近1说明算法输出的结果越接近真实的情况.对于合成网络数据，存在标准的社区划分结果，而大部分的真实网络并没有标准的结果，因此实验采用模块度Qov[22]来分析算法在真实网络中运行的效果.5.1.2 合成网络实验LFR网络[21]通过模拟不同特性的真实网络，可从多个角度测试算法的性能.实验选取LFR网络的三个参数(om、μ和on/N)来验证算法的NMI值，其中om为重叠结点拥有的标签数；μ表示结点与社区外部结点链接的概率，随着μ值增大，结点的社区外部链接增多，导致合成网络结构变得更加复杂，社区发现的难度也随之增加；on/N表示重叠结点占网络结点的比例.当实验观测其中某参数变化时，其他参数不变.实验结果如图3(a)、3(b)、3(c)所示，MLPS算法的NMI值最优，表明MLPS算法在处理不同特性的网络时能够取得较好的准确度.图3(d)分析了三种算法在网络边数从104增长到106时的运行效率，结果显示了这三种算法都具有接近线性的时间复杂度.5.1.3 真实网络实验本文选取7个不同的真实网络，如表1所示，其中C-DBLP1和C-DBLP2是从WAMDM实验室提供的数据库中抽取得到的两个不同规模的学者合著网络.表1比较了MLPS、MLPA和COPRA算法取最优参数时的平均模块度Qov和方差Std.，结果显示本文提出的MLPS算法能够取得较好的效果.5.2 SHCDA实验本节实验包含Coauthor实验和新浪微博实验.Coauthor数据集[9]存在可对比的实验结果，能够验证SHCDA算法的准确度；新浪微博数据集通过爬虫程序抓取，从一个特定用户开始，抓取最近发表的微博中转发数较高的微博及转发该微博的用户，并以广度优先的策略循环抓取数据，最后整理出63,641个用户及1,391,718条用户关系，其中包含27,759条微博转发关系.5.2.1 Coauthor实验Coauthor数据集包含28个计算机相关的会议，涉及六个研究领域，如表2所示.每个领域都拥有一组程序委员会成员，我们认为不同领域间的共同委员会成员即为这些领域间的结构洞.该数据集包含1718个委员会成员，其中拥有107个结构洞. 根据上述六个领域的相关性，本文选取三对领域(AI-DM，DB-DM和DP-NC)来验证算法的准确度.同时实验选取PageRank[28]、COPRA和MLPA算法进行对比分析，如图4、图5和图6所示.本文提出的SHCDA算法在top-30之前都能取得最好的效果，而且从三个图中可以发现，PageRank选取的重要结点大部分都不是结构洞，因此结构洞在网络中可能只是一些普通结点，却扮演着极其重要的角色.5.2.2 新浪微博实验在微博、Twitter等社交网络中，社区间的结构洞是不同群体进行信息传播的桥梁，一般存在于微博的转发路径中[9].因此，本文定义Precision来衡量SHCDA算法的准确性：其中,Nsh(k)表示SHCDA算法输出的top-k结构洞，Nf(k)是Nsh(k)中存在转发微博行为的结点集合.实验结果如图7所示，显示出本文提出的SHCDA算法取得了最优的准确性，能够有效地挖掘出社区间的结构洞.本文还考察了结构洞的重要性对社区间的信息传播的影响.针对算法输出的top-k结构洞，定义Rg表示在固定步长下存在转发行为的结点相对增长数：其中,C为增长步长，本节实验中C取50.从图8中可以看出SHCDA算法在top-200前有较快的增幅，而后趋于稳定，说明重要度较高的结构洞更容易进行社区间的信息传播，这对社会网络的信息传播机制研究和舆情监控具有重要的指导意义. 为提高大数据环境下重叠社区发现的效果，本文结合结点间的相似性传播和影响传播两种方式，提出了基于多标签传播方式的重叠社区发现算法(MLPS)，实验验证了该算法取得了较高的准确度和模块度，且具有接近线性的时间复杂度；同时,基于MLPS算法的输出结果，本文针对重叠结构进行分析，提出了社区间的结构洞识别算法(SHCDA)，在不同特性数据集的实验显示了该算法拥有较高的准确度.刘世超男，1989年2月出生，河南周口人.武汉大学计算机学院博士生，研究方向为社会网络分析和Web数据挖掘.E-mail:************.cn朱福喜(通讯作者) 男，1957年7月出生，湖北武汉人.武汉大学计算机学院教授、博士生导师，主要从事人工智能和Web数据挖掘.E-mail:*************.cn冯曦女，1991年11月出生，陕西西安人.武汉大学计算机学院硕士生,研究方向为社会网络分析和数据挖掘.E-mail:*********************【相关文献】[1]Girvan M,Newman M E munity structure in social and biologicalnetworks[J].Proceedings of the National Academy of Sciences,2002,99(12):7821-7826. [2]Palla G,Derényi I,Farkas I,et al.Uncovering the overlapping community structure of complex networks in nature and society[J].Nature,2005,435(7043):814-818.[3]Shi C,Cai Y,Fu D,et al.A link clustering based overlapping community detectionalgorithm[J].Data & Knowledge Engineering,2013,87:394-404.[4]Whang J J,Gleich D F,Dhillon I S.Overlapping community detection using seed set expansion[A].CIKM 2013[C].San Francisco,CA,USA,ACM,2013.2099-2108.[5]Burt R S.Structural Holes:The Social Structure of Competition[M].MA,Harvard University Press,1992.[6]Kleinberg J,Suri S,Tardos é,et al.Strategic network formation wi th structuralholes[A].Proceedings of the 9th ACM Conference on ElectronicCommerce[C].Chicago,Illinois,USA,ACM,2008.284-293.[7]Buskens V,Van de Rijt A.Dynamics of networks if everyone strives for structuralholes[J].American Journal of Sociology,2008,114(2):371-407.[8]李泓波,等.基于拓扑势的重叠社区及社区间结构洞识别.电子学报,2014,42(1):62-69.Li H B,et al.Identification of overlapping communities and structural holes between communities based on topological potential[J].Acta Electronica Sinica,2014,42(1):62-69.(in Chinese)[9]Lou T,Tang J.Mining structural hole spanners through information diffusion in social networks[A].WWW 2013[C].Rio de Janeiro,Brazil,International World Wide Web Conferences Steering Committee,2013.825-836.[10]Raghavan U N,Albert R,Kumara S.Near linear time algorithm to detect community structures in large-scale networks[J].Physical Review E,2007,76(3):036106.[11]Barber M J,Clark J W.Detecting network communities by propagating labels under constraints[J].Physical Review E,2009,80(2):026129.[12]Liu X,Murata T.Advanced modularity-specialized label propagation algorithm for detecting communities in networks[J].Physica A:Statistical Mechanics and its Applications,2010,389(7):1493-1500.[13]Xie J,Szymanski B munity detection using a neighborhood strength driven label propagation algorithm[A].NSW 2011[C].New York,USA,IEEE,2011.188-195.[14]Gregory S.Finding overlapping communities in networks by label propagation[J].New Journal of Physics,2010,12(10):103018.[15]Wu Z H,Lin Y F,Gregory S,et al.Balanced multi-label propagation for overlapping community detection in social networks[J].Journal of Computer Science and Technology,2012,27(3):468-479.[16]Xie J,Szymanski B K,Liu X.Slpa:Uncovering overlapping communities in social networks via a speaker-listener interaction dynamic process[A].ICDMW2011[C].Vancouver,BC,Canada,IEEE,2011.344-349.[17]Dai Q,Guo M,Liu Y,et al.MLPA:Detecting overlapping communities by multi-label propagation approach[A].CEC 2013[C].Cancun,Mexico,IEEE,2013.681-688.[18]Aral S,Walker D.Identifying influential and susceptible members of socialnetworks[J].Science,2012,337(6092):337-341.[19]Li Q,et al.Identifying influential spreaders by weighted LeaderRank[J].PhysicaA:Statistical Mechanics and its Applications,2014,404:47-55.[20]Wang Y,Feng X.A Potential-Based Node Selection Strategy for Influence Maximization in a Social Network[M].Advanced Data Mining and Applications.Springer Berlin Heidelberg,2009.350-361.[21]Lancichinetti A,Fortunato S,Radicchi F.Benchmark graphs for testing community detection algorithms[J].Physical Review E,2008,78(4):046110.[22]Nicosia V,Mangioni G,Carchiolo V,et al.Extending the definition of modularity to directed graphs with overlapping communities[J].Journal of Statistical Mechanics:Theory and Experiment,2009,2009(03):P03024.[23]Zachary W.An information flow model for conflict and fission in smallgroups1[J].Journal of anthropological research,1977,33(4):452-473.[24]Lusseau D,Schneider K,Boisseau O J,et al.The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations[J].Behavioral Ecology and Sociobiology,2003,54(4):396-405.[25]Girvan M,Newman M E munity structure in social and biologicalnetworks[J].Proceedings of the National Academy of Sciences,2002,99(12):7821-7826. [26]Newman M E J.Finding community structure in networks using the eigenvectors of matrices[J].Physical review E,2006,74(3):036104.[27]Newman M E J.The structure of scientific collaboration networks[J].Proceedings of the National Academy of Sciences,2001,98(2):404-409.[28]Page L,Brin S,Motwani R,et al.The PageRank citation ranking:Bringing order to the web[R].Stanford InfoLab,1999-66.。