本发明涉及互联网
技术领域：
，尤其涉及一种度量社会网络影响力的方法。
背景技术：
：近年来，互联网技术的飞速发展促进了twitter，微博和微信等社交网络的发展。社交网络是具有个体之间错综复杂关系的网络，它促进了信息在个体之间的传播。影响力最大化(influencemaximization,im)的目的是确定一定数量的最具影响力的用户，通过信息扩散使最终受影响的用户的预期数量最大化。由于其广泛的实际应用，如病毒营销[1,2]，谣言控制[3,4]和级联检测[5]，影响最大化引起了研究人员和专家的极大关注。im问题首先由kempe等人[6]提出，证明了其是np难问题，并提出了具有保证求解精度的贪心算法。传统的贪心算法具有较高的时间复杂度，因此无法应用于规模较大的网络。为了解决这个问题，近年来研究者提出了许多近似算法和启发式方法，例如基于仿真的算法[5,7]，基于中心度的算法[8,9,10]，基于路径的算法[11，12,13]和基于社区的算法[14,15,16,17,18]。基于社区的算法通常利用社区中节点的影响来近似其对整个网络的影响。社区结构[19]是网络最突出的特征之一，其被描述为一个特殊的群体，其中节点在社区内连接紧密，而在社区间连接稀疏。它揭示了网络的组织结构和功能组件，并从中观层面描述了网络的结构。对于社区中的两个节点，即使由于数据的稀疏性，它们在微观结构中仅具有弱关系，但由于社区结构的限制，它们之间的影响将得到加强。另外，由于一个人的影响范围是有限的，因此可以用一个社区的影响来近似其对整个网络的影响。利用社区的规模比整个网络小得多的优势，可以在保证解决方案精度的情况下更有效地计算节点的影响力；现有的基于社区的im算法已经取得了一些成果，例如cofim[17]和impc[18]。但是，这些算法仅考虑了社区中节点的数量，而忽略了社区中边的连接密度。如图1(a)所描述的具有社区结构的网络，社区c3与c4中有相同数量的节点，但是中的边数比.c3.中的要多。仅考虑节点数量，两个社区的影响是相同的。但是，社区中边的数量越多，表明节点之间进行交互的可能性就越高，这可能会增加激活非激活节点的机会。因此，区分c3和.c4.的影响有利于更准确地度量节点的影响力。另外，现有方法只能应用于非重叠的社区结构。但在现实世界中，社区通常是重叠的，即一个节点可能属于许多社区。例如，在图1(b)中，节点v1属于c1，和c4三个社区，因此其对三个社区中的节点都具有影响。im的研究一直是社会网络分析中的热门研究课题，旨在寻找社交网络中最具影响力的用户，以最大程度地扩大影响力。近年来，许多研究都集中在im的问题上，利用小规模社区结构来提高运行效率。但是，现有的基于社区的影响力最大化方法仅考虑社区中节点的数量，而忽略社区中节点之间连接的密度。此外，现有研究方法只能应用于非重叠的社区结构。技术实现要素：本发明的目的就在于为了解决上述问题而提供一种度量社会网络影响力的方法。本发明通过以下技术方案来实现上述目的：本发明包括以下步骤：问题定义：给定一个网络g，目标是选择一组最具影响力的节点s，在特定的扩散模型下最大化预期的总激活节点数σ(s)：s*＝argsmaxσ(s)(1)影响力度量：设一个激活节点u的影响扩散过程分为两个阶段，一个阶段称为多邻居传播，另一个阶段称为社区传播；(1)多邻居影响：在多邻居传播过程中，影响传播的两个步骤：首先，影响从节点u传播到n(u)，这是u对n(u)的直接影响；然后影响将继续从n(u)中的激活节点传播到n(n(u))，这是节点u通过n(u)对n(n(u))的间接影响；对于每个激活节点u，通过这种信息级联扩散的方式，其对两跳以上的邻居影响较小，很难间接激活它们；因此仅考虑其对一跳邻居n(u)和两跳邻居n(n(u))的影响；设puv表示u对v的影响概率，in1(u)和in2(u)分别表示节点u对一跳邻居和两跳邻居的影响，则in1(u)和in2(u)被定义为等式(2)[20]和(3)；然后，将节点u的多邻居影响表示为f1(u)，用以下公式近似表示：f1(u)＝in1(u) in2(u)(4)由于n(u)和n(n(u))是u直接和间接邻居，因此u对n(u)的影响是直接的，而u对n(n(u))的影响是间接的；直接影响大于间接影响，因此n(u)中的节点更有可能被u激活；如果仅考虑激活节点u的影响，则在多邻居传播之后，n(u)包含的激活节点比例要大于n(n(u))中激活节点的比例；(2)社区影响：由于激活节点对bc(u)和nc(u)以外的其他社区影响较小，为简化起见，忽略了对除bc(u)和nc(u)以外的其他社区的影响；激活节点在bc(u)中的影响称为社区内影响，而激活节点在nc(u)中的影响称为社区间影响；基于社区中节点之间的平均最短距离定义社区紧密度的概念；给出了社区内影响和社区间影响的定义；定义1.社区紧密度.假设ci是一个社区，d(u,v)min是节点u和v之间的最短路径，u,v∈ci，则该社区ci的紧密度定义为：close(ci)是社区ci中节点的平均最短路径，它反映了ci中边的连接密度，close(ci)值越小表明ci的影响越大；(2.1)社区内影响社区内影响度量了bc(u)中激活的节点对bc(u)中的非激活节点的影响；设ai表示社区ci∈bc(u)中激活的节点，则影响将从ai扩散到ci中的非激活节点；在级联扩散过程中，影响力会随着路径长度的增加而减小；显然，ai中的激活节点和ci中的非激活节点之间的路径越短则表明非激活节点越容易被激活；ci中的非激活节点到ai的平均路径表示为cd(u,ci,ai)，其定义为：其中d(v,ai)min表示为节点v到ai的最短路径，|ci/(u∪ai)|表示社区ci中非激活节点的数量，cd(u,ci,ai)是考虑了ai的社区紧密度的一种变体；cd(u,ci,ai)的值越小，表明社区ci中的节点与ai的联系越紧密，因此ai对社区ci的影响就越大；当影响在社区中传播时，社区中的影响力不仅取决于社区的紧密程度，还取决于社区中节点的数量；社区中节点越多意味着可能会有更多的节点被激活；因此，我们将社区中的节点数标准化为社区的权重，表示为因此，越大并且cd(u,ci,ai)越小，表明社区ci的影响力更大；因此，我们通过结合权重和社区的紧密度来度量节点的社区内影响，记为ic1(u)，其定义为：(2.2)社区间影响社区间影响度量了nc(u)中的激活节点对nc(u)中的非激活节点的影响；由于节点u∈ci与邻居社区cj∈nc(u)之间的连接稀疏，因此对于每个cj，cj中的激活节点数量(aj)很小，因此aj对社区cj的影响相对较小；忽略了影响从aj到nc(u)的传播过程，并用社区自身的影响力来估计节点u的社区间影响；与社区内影响相同，我们结合社区的权重和紧密度来度量社区cj的影响力，记为i(cj)，其定义为：节点u∈ci的社区间影响表示为ic2(u)，可以近似为：然后，我们将社区内和社区间的影响整合为节点u的社区影响力，表示为f2(u)：f2(u)＝α·ic1(u) β·ic2(u)(9)其中α和β分别表示社区内影响和社区间影响的权重；(3)总影响将多邻居影响和社区影响整合为整个网络中节点u的总影响，记为f(u)，本发明方法有助于更全面地度量节点的影响力；f(u)＝f1(u) f2(u)＝[in1(u) in2(u)] [α·ic1(u) β·ic2(u)](10)。本发明的有益效果在于：本发明是一种度量社会网络影响力的方法，与现有技术相比，本发明以有效地选择种子节点。算法1显示了ccim算法的伪代码。首先，通过社区检测算法将网络g(v,e)划分为m个社区，然后计算节点的影响并找到影响力最大的种子节点。为了避免重复计算，我们采用边际增益策略的增量计算。选择种子节点后，删除重叠影响并重新计算其余节点的影响。最后，种子节点以特定的扩散模型在网络中传播影响力以最大化影响范围。附图说明图1是具有社区结构的网络；图中a非重叠社区；b重叠社区图2是本发明的网络划分为4个社区示意图。具体实施方式下面结合附图对本发明作进一步说明：首先介绍了本发明用到的相关符号，其次明确了本发明需要解决的问题，最后介绍了度量节点影响力的主要方法。1.相关符号给定网络g(v,e)，其中v是节点集，e是边集。假设网络被划分为m个社区，记为c＝{c1,c2,...,cm}，其中节点在社区内连接紧密，而在社区之间连接稀疏。对于任何节点u∈v，它可能属于一个或多个社区。如果u∈ci,ci称为u的所属社区。设bc(u)表示为u的所属社区的集合，|bc(u)|≥1。在g中，如果节点v与节点u直接相连，则v称为u的邻居或单跳邻居。节点邻居的邻居称为节点的两跳邻居。我们用n(u)表示u的一跳邻居集，n(n(u))表示u的两跳邻居集。如果u∈ci,但其邻居节点v∈cj(i≠j)，则cj称为节点u的邻居社区。令nc(u)表示为u的邻居社区集合，|nc(u)|≥0。在信息传播过程中，每个节点都处于激活或非激活两种状态之一。激活状态表示该节点已经接受了暴露给它的信息，并且可以将该信息转发给其邻居，而非激活状态意味着该节点尚未接受该信息。当非激活节点受到激活节点的影响时，它们的状态将会从非激活状态更改为激活状态，反之则不行。一个激活节点u首先尝试影响其邻居节点而激活的邻居进一步影响其邻居n(v)。2.问题定义给定一个网络g，我们的目标是选择一组最具影响力的节点s，在特定的扩散模型下最大化预期的总激活节点数σ(s)：s*＝argsmaxσ(s)(1)解决上述问题的关键是如何度量节点的影响。3.影响力度量我们假设一个激活节点u的影响扩散过程分为两个阶段，一个阶段称为多邻居传播，另一个阶段称为社区传播。多邻居传播考虑了点对点的影响，反映了微观层面的影响。社区传播考虑了点对社区的影响，反映了中观层面的影响。同时考虑微观和中观影响有利于从多个层面和多个角度准确地测量节点在网络中的影响。(1)多邻居影响在多邻居传播过程中，我们关注影响传播的两个步骤。首先，影响从节点u传播到n(u)，这是u对n(u)的直接影响。然后影响将继续从n(u)中的激活节点传播到n(n(u))，这是节点u通过n(u)对n(n(u))的间接影响。对于每个激活节点u，通过这种信息级联扩散的方式，其对两跳以上的邻居影响较小，很难间接激活它们。因此本发明仅考虑其对一跳邻居n(u)和两跳邻居n(n(u))的影响。设puv表示u对v的影响概率，in1(u)和in2(u)分别表示节点u对一跳邻居和两跳邻居的影响，则in1(u)和in2(u)被定义为等式(2)[20]和(3)。然后，将节点u的多邻居影响表示为f1(u)，用以下公式近似表示：f1(u)＝in1(u) in2(u)(4)由于n(u)和n(n(u))是u直接和间接邻居，因此u对n(u)的影响是直接的，而u对n(n(u))的影响是间接的。通常，直接影响大于间接影响，因此n(u)中的节点更有可能被u激活。如果仅考虑激活节点u的影响，则在多邻居传播之后，n(u)包含的激活节点比例要大于n(n(u))。(2)社区影响：在多邻居传播之后，n(u)和n(n(u))中的一些节点被激活，这些节点将进一步影响网络中的其余未激活节点。n(u)和n(n(u))中的节点可能分散在不同的社区中，因此影响可以传播到不同的社区。这个阶段的关键问题是如何分析计算影响从n(u)和n(n(u))传播到其他不同的社区。n(u)中的节点可能分散在bc(u)(u的所属社区的集合)和nc(u)(u的邻居社区的集合)中，而n(n(u))中的节点可能会分散在bc(u)，nc(u)和其他社区。为了简化起见，我们忽略了除bc(u)和nc(u)以外的其他社区中节点的影响。在本发明中，激活节点在bc(u)中的影响称为社区内影响，而激活节点在nc(u)中的影响称为社区间影响。节点在社区中的影响不仅取决于社区中节点的数量，还取决于社区中节点之间的关系。社区中的节点越多，影响范围就越大；节点之间的关系越紧密，影响强度就越大。为了定量地度量观察结果，我们基于社区中节点之间的平均最短距离定义社区紧密度的概念。然后，我们给出了社区内影响和社区间影响的定义。定义1.社区紧密度.假设ci是一个社区，d(u,v)min是节点u和v之间的最短路径，u,v∈ci，则该社区ci的紧密度定义为：close(ci)是社区ci中节点的平均最短路径，它反映了ci中边的连接密度，close(ci)值越小表明ci的影响越大。(2.1)社区内影响社区内影响度量了bc(u)中激活的节点对bc(u)中的非激活节点的影响。设ai表示社区ci∈bc(u)中激活的节点，则影响将从ai扩散到ci中的非激活节点。在级联扩散过程中，影响力会随着路径长度的增加而减小。显然，ai中的激活节点和ci中的非激活节点之间的路径越短则表明非激活节点越容易被激活。ci中的非激活节点到ai的平均路径表示为cd(u,ci,ai)，其定义为：其中d(v,ai)min表示为节点v到ai的最短路径，|ci/(u∪ai)|表示社区ci中非激活节点的数量，cd(u,ci,ai)是考虑了ai的社区紧密度的一种变体。cd(u,ci,ai)的值越小，表明社区ci中的节点与ai的联系越紧密，因此ai对社区ci的影响就越大。当影响在社区中传播时，社区中的影响力不仅取决于社区的紧密程度，还取决于社区中节点的数量。社区中节点越多意味着可能会有更多的节点被激活。因此，我们将社区中的节点数标准化为社区的权重，表示为因此，越大并且cd(u,ci,ai)越小，表明社区ci的影响力越大。因此，我们通过结合权重和社区的紧密度来度量节点的社区内影响，记为ic1(u)，其定义为：(2.2)社区间影响社区间影响度量了nc(u)中的激活节点对nc(u)中的非激活节点的影响。由于节点u∈ci与邻居社区cj∈nc(u)之间的连接稀疏，因此对于每个cj，cj中的激活节点数量(aj)很小，因此aj对社区cj的影响相对较小。因此，为了提高计算效率，我们忽略了影响从aj到nc(u)的传播过程，并用社区自身的影响力来估计节点u的社区间影响。与社区内影响相同，我们结合社区的权重和紧密度来度量社区cj的影响力，记为i(cj)，其定义为：节点u∈ci的社区间影响表示为ic2(u)，可以近似为：然后，我们将社区内和社区间的影响整合为节点u的社区影响力，表示为f2(u)：f2(u)＝α·ic1(u) β·ic2(u)(9)其中α和β分别表示社区内影响和社区间影响的权重。(3)总影响我们将多邻居影响和社区影响整合为整个网络中节点u的总影响，记为f(u)，有助于更全面地衡量节点的影响力。f(u)＝f1(u) f2(u)＝[in1(u) in2(u)] [α·ic1(u) β·ic2(u)](10)本发明提出基于社区紧密度的影响最大化(ccim)算法，以有效地选择种子节点。算法1显示了ccim算法的伪代码。首先，通过社区检测算法将网络g(v,e)划分为m个社区，然后计算节点的影响并找到影响力最大的种子节点。为了避免重复计算，我们采用边际增益策略的增量计算。选择种子节点后，删除重叠影响并重新计算其余节点的影响。最后，种子节点以特定的扩散模型在网络中传播影响力以最大化影响范围。实施例：社会网络中基于社区紧密度的影响力最大化该方法主要包括三个步骤：(1)社区检测(2)影响力度量(3)扩散过程，下面分别详细介绍每一个步骤。(1)社区检测通过社区检测算法将网络g(v,e)划分为m个社区，例如图2,将网络划分为4个社区。社区c1包含节点v0,v1,v2,v3,v4，社区c2包括节点v5,v6,v7,v8,v9,v10，社区c3包含节v4,v11,v12,v13,v14,v15,v16,v17，社区c4包含节点v4,v18,v19,v20,v21,v22,v23。(2)影响力度量根据公式(4)计算各个节点的多邻居影响，结果如表1所示。表1.多邻居影响根据公式(6)计算各个节点的社区内影响，结果如表2所示。表2.社区内影响节点社区内影响节点社区内影响节点社区内影响v00.000222v80.6002v162.25025v10.000167v90.66689v172.400267v20.0v100.6002v181.33355v30.000167v112.25025v191.000167v43.7435841v122.500278v201.500249v50.6002v132.4002667v211.33355v60.66689v142.00022v221.500249v70.6002v152.400267v231.000167根据公式(8)计算各个节点的社区间影响，结果如表3所示。表3.社区间影响节点社区间影响节点社区间影响节点社区间影响v00.0v80.0v160.840285v10.0v90.0v170.0v21.99095v100.0v181.150959v31.99095v110.840285v191.150958v40.375125v120.0v200.0v50.0v130.0v210.0v61.9910988v140.0v220.0v70.0v150.0v230.0根据公式(10)计算各个节点的总影响，我们设α＝0.5β＝0.2，结果如表4所示。表4.总影响节点社区间影响节点社区间影响节点社区间影响v01.2719355v81.92509925v163.6074650v11.9445267v92.785825v172.97989375v22.857316v101.92509925v182.7489924v32.067717v113.7046879v193.149440v45.73185v122.521963v202.2045293v51.835814v133.1941795v212.688324v63.629282v142.9167755v222.2045293v71.835814v152.97989375v233.0293676(3)扩散过程我们选取一个节点作为种子节点，在传统的独立级联模型(ic)下进行信息扩散，对于ic模型，每个激活的节点都有一次激活其非激活邻居的机会，从u到v的传播概率定义为puv＝1/kv，其中kv表示节点v的度。在实验过程中，设每个节点的激活阈值为随机数，为了消除结果的偶然性，通过执行10000次蒙特卡洛(mc)仿真来估计影响扩散值，结果如表5所示。表5.影响数量节点影响数量节点影响数量节点影响数量v02.258v82.6415v163.7167v12.933v93.3569v173.0882v23.401v102.6445v183.268v32.9126v113.8922v193.759v45.5802v122.4494v202.659v52.6066v133.2343v213.1741v64.0219v143.1379v222.6506v72.5854v153.1412v233.5672参考文献：1.domingos,p.,richardson,m.:miningthenetworkvalueofcustomers.in:proceedingsofthe7thacmsigkddinternationalconferenceonknowledgediscoveryanddatamining,pp.57-66.kdd,sanfrancisco(2001).2.richardson,m.,domingos,p.:miningknowledge-sharingsitesforviralmarketing.in:proceedingsofthe8thacmsigkddinternationalconferenceonknowledgediscoveryanddatamining,pp.61-70.kdd,edmonton(2002).3.budak,c.,agrawal,d.,abbadi,a.-e.:limitingthespreadofmisinformationinsocialnetworks.in:proceedingsofthe20thinternationalconferenceonworldwideweb,pp.665-674.www,hyderabad.(2011)4.he,x.,song,g.,chen,w.:influenceblockingmaximizationinsocialnetworksunderthecompetitivelinearthresholdmodel.in:proceedingsofthe12thsiaminternationalconferenceondatamining,pp.463-474.sdm,anaheim(2011).5.leskovec,j.,krause,a.,guestrin,c.:cost-effectiveoutbreakdetectioninnetworks.in:proceedingsofthe13thacmsigkddinternationalconferenceonknowledgediscoveryanddatamining,pp.420–429.acm,sanjose(2007).6.kempe,d.,kleinberg,j.,tardos,e.:maximizingthespreadofinfluencethroughasocialnetwork.in:proceedingsofthe9thacmsigkddinternationalconferenceonknowledgediscoveryanddatamining,pp.137-146.acm,washington(2003).7.goyal,a.,lu,w.,lakshmanan,l.v.:celf :optimizingthegreedyalgorithmforinfluencemaximizationinsocialnetworks.in:proceedingsofthe20thinternationalconferencecompaniononworldwideweb,pp.47–48.acm,(2011).8.chen,w.,wang,y.,yang,s.:efficientinfluencemaximizationinsocialnetworks.in:proceedingsofthe15thacmsigkddinternationalconferenceonknowledgediscoveryanddatamining,pp.199–208.acm,paris(2009).9.liu,h.-l.,ma,c.,xiang,b.-b.:identifyingmultipleinfluentialspreadersbasedongeneralizedclosenesscentrality.physicaa492,2237–2248(2018).10.zhu,j.,liu,y.,yin,x.:anewstructure-hole-basedalgorithmforinfluencemaximizationinlargeonlinesocialnetworks,ieeeaccess5,23405–23412(2017).11.kim,j.,kim,s.-k.,yu,h.:scalableandparallelizableprocessingofinfluencemaximizationforlarge-scalesocialnetworks.in:29thieeeinternationalconferenceondataengineering,pp.266–277.ieee,brisbane(2013).12.liu,b.,cong,g.,zeng,y.:influencespreadingpathanditsapplicationtothetimeconstrainedsocialinfluencemaximizationproblemandbeyond.ieeetrans.knowl.dataeng.26(8),1904–1917(2014).13.ko,y.-y.,chae,d.-k.,kim,s.-w.:accuratepath-basedmethodsforinfluencemaximizationinsocialnetworks.in:proceedingsofthe25thinternationalconferencecompaniononworldwideweb,pp.59–60.www,geneva(2016).14.galstyan,a.,musoyan,v.:maximizinginfluencepropagationinnetworkswithcommunitystructure.physicalreviewe79(2),056102(2009).15.cao,t.,wu,x.,wang,s.,hu,x.:oasnet:anoptimalallocationapproachtoinfluencemaximizationinmodularsocialnetworks.in:acmsymposiumonappliedcomputing,pp.1088–1094.sac,sierre(2010).16.wang,y.,cong,g.,song,g.:community-basedgreedyalgorithmforminingtop-kinfluentialnodesinmobilesocialnetwork.in:proceedingsofthe16thacmsigkddinternationalconferenceonknowledgediscoveryanddatamining,pp.1039-1048.acm,washington(2010).17.shang,j.,zhou,s.,li,x.:cofim:acommunity-basedframeworkforinfluencemaximizationonlarge-scalenetworks.knowledge-basedsystems117,88-100(2017).18.shang,j.,wu,h.:impc:influencemaximizationbasedonmulti-neighborpotentialincommunitynetworks.physicaa512,1085-1103(2018).19.girvan,m.,newman,m.e.j.:communitystructureinsocialandbiologicalnetworks.procnatlacadsciusa99(12),7821-7826(2002).20.wang,y.,feng,x.:apotential-basednodeselectionstrategyforinfluencemaximizationinasocialnetwork.lecturenotesincomputerscience5678,350-361(2009).lancichinetti,a.,fortunato,s.,radicchi,f.:benchmarkgraphsfortestingcommunitydetectionalgorithms.physicalreviewe78(4pt2),046110(2008).以上显示和描述了本发明的基本原理和主要特征及本发明的优点。本行业的技术人员应该了解，本发明不受上述实施例的限制，上述实施例和说明书中描述的只是说明本发明的原理，在不脱离本发明精神和范围的前提下，本发明还会有各种变化和改进，这些变化和改进都落入要求保护的本发明范围内。本发明要求保护范围由所附的权利要求书及其等效物界定。当前第1页1 2 3
技术特征：1.一种度量社会网络影响力的方法，其特征在于，包括以下步骤：
问题定义：
给定一个网络g，目标是选择一组最具影响力的节点c2c4s，在特定的扩散模型下最大化预期的总激活节点数σ(s)：
s*＝argsmaxσ(s)(1)
影响力度量：
设一个激活节点u的影响扩散过程分为两个阶段，一个阶段称为多邻居传播，另一个阶段称为社区传播；
(1)多邻居影响：
在多邻居传播过程中，影响传播的两个步骤：首先，影响从节点u传播到n(u)，这是u对n(u)的直接影响；然后影响将继续从n(u)中的激活节点传播到n(n(u))，这是节点u通过n(u)对n(n(u))的间接影响；对于每个激活节点u，通过这种信息级联扩散的方式，其对两跳以上的邻居影响较小，很难间接激活它们；因此仅考虑其对一跳邻居n(u)和两跳邻居n(n(u))的影响；
设puv表示u对v的影响概率，in1(u)和in2(u)分别表示节点u对一跳邻居和两跳邻居的影响，则in1(u)和in2(u)被定义为等式(2)[20]和(3)；
然后，将节点u的多邻居影响表示为f1(u)，用以下公式近似表示：
f1(u)＝in1(u) in2(u)(4)
由于n(u)和n(n(u))是u直接和间接邻居，因此u对n(u)的影响是直接的，而u对n(n(u))的影响是间接的；直接影响大于间接影响，因此n(u)中的节点更有可能被u激活；如果仅考虑激活节点u的影响，则在多邻居传播之后，n(u)包含的激活节点比例要大于n(n(u))中激活节点的比例；
(2)社区影响：
由于激活节点对bc(u)和nc(u)以外的其他社区影响较小，为简化起见，忽略了对除bc(u)和nc(u)以外的其他社区的影响；激活节点在bc(u)中的影响称为社区内影响，而激活节点在nc(u)中的影响称为社区间影响；
基于社区中节点之间的平均最短距离定义社区紧密度的概念；给出了社区内影响和社区间影响的定义；
定义1.社区紧密度.假设ci是一个社区，d(u,v)min是节点u和v之间的最短路径，u,v∈ci，则该社区ci的紧密度定义为：
close(ci)是社区ci中节点的平均最短路径，它反映了ci中边的连接密度，close(ci)值越小表明ci的影响越大；
(2.1)社区内影响
社区内影响度量了bc(u)中激活的节点对bc(u)中的非激活节点的影响；设ai表示社区ci∈bc(u)中激活的节点，则影响将从ai扩散到ci中的非激活节点；
在级联扩散过程中，影响力会随着路径长度的增加而减小；显然，ai中的激活节点和ci中的非激活节点之间的路径越短则表明非激活节点越容易被激活；ci中的非激活节点到ai的平均路径表示为cd(u,ci,ai)，其定义为：
其中d(v,ai)min表示为节点v到ai的最短路径，|ci/(u∪ai)|表示社区ci中非激活节点的数量，cd(u,ci,ai)是考虑了ai的社区紧密度的一种变体；cd(u,ci,ai)的值越小，表明社区ci中的节点与ai的联系越紧密，因此ai对社区ci的影响就越大；
当影响在社区中传播时，社区中的影响力不仅取决于社区的紧密程度，还取决于社区中节点的数量；社区中节点越多意味着可能会有更多的节点被激活；因此，我们将社区中的节点数标准化为社区的权重，表示为wci；因此，wci越大并且cd(u,ci,ai)越小，表明社区ci的影响力更大；因此，我们通过结合权重和社区的紧密度来度量节点的社区内影响，记为ic1(u)，其定义为：
(2.2)社区间影响
社区间影响度量了nc(u)中的激活节点对nc(u)中的非激活节点的影响；由于节点u∈ci与邻居社区cj∈nc(u)之间的连接稀疏，因此对于每个cj，cj中的激活节点数量(aj)很小，因此aj对社区cj的影响相对较小；忽视影响从aj到nc(u)的传播过程，并用社区自身的影响力来估计节点u的社区间影响；与社区内影响相同，我们结合社区的权重和紧密度来度量社区cj的影响力，记为i(cj)，其定义为：
节点u∈ci的社区间影响表示为ic2(u)，可以近似为：
然后，我们将社区内和社区间的影响整合为节点u的社区影响力，表示为f2(u)：
f2(u)＝α·ic1(u) β·ic2(u)(9)
其中α和β分别表示社区内影响和社区间影响的权重；
(3)总影响
将多邻居影响和社区影响整合为整个网络中节点u的总影响，记为f(u)，有助于更全面地衡量节点的影响力；
f(u)＝f1(u) f2(u)＝[in1(u) in2(u)] [α·ic1(u) β·ic2(u)](10)。
技术总结本发明公开了一种度量社会网络影响力的方法，本发明以有效地选择种子节点。算法1显示了CCIM算法的伪代码。首先，通过社区检测算法将网络G(V,E)划分为M个社区，然后计算节点的影响并找到影响力最大的种子节点。为了避免重复计算，我们采用边际增益策略的增量计算。选择种子节点后，删除重叠影响并重新计算其余节点的影响。最后，种子节点以特定的扩散模型在网络中传播影响力以最大化影响范围。
技术研发人员：吴晴晴;周丽华;黄亚群
受保护的技术使用者：云南大学
技术研发日：2020.01.20
技术公布日：2020.06.05
