实验室-计算机技术

:复杂网络最大自然界中存在的大量复杂系统都可以通过形形的网络加以描述。一个典型的网络是由许多节点与连接两个节点之间的一些边组成的，其点用来代表真实系统中不同的，而边则用来表示之间的关系，通常是当两个节点之间具有某种特定的关系时连一条边，反之则不连边。有边相连的两个，而社会网络则是指由社会来作为节点间的关联关系作为边所形成的具有复杂关系的网，的发张。对于组织，如何能根据社会网络节点，迅速的定位分子的头目或者一些关键的，进而可以有效的监视和控制组织，甚至捣毁他们，从而社会的稳定，促进人类文明的发张。在疾病防治领域，许多的传染性疾病，如流感、以及其他疾病也对人类产生巨大的。如果可以在发生时，能够通过对这一社会网络的分析来控制这些疾病的显得尤为重要。如果病的进一步扩散，从而可以将损失尽量的减少。而这些都可以通过社会网络中的最大化问题加以解常用的模常用的模型有SI、SIR、SIS、ICM、LTM等，此外也有一些其他的模型，如投票者模型。它S:即根据通常所见到的疾病传染过程所生成的模型。对于网络中的每一个节点只有两种状态，即已状态（）和未状态（S。对意的已节点，它都可能其处未三个状态，即已状态（I，未状态（S）和已康复状态（R。它的过程通常如下：的免疫功能一样，它将获得对该种疾病的免疫能力，即该节点不可能被再次。SIS:根据人类对某些疾病的反复特性所建立起来的模型。它对于网络中的每一个节点都（S恢复为未状态，并且在以后的过程中可能再次变为已状态。tv的邻居节点w变成活跃状态，此时它有使处在未激活状态的节点v变越大，即越大，则v容易被激活。ICM相同，网络中的每个节点只有活跃和不活跃两种状态，节点只能由未激活状态转变N(v)wN(v)，定义邻居节点w对它的权值为，表示节点w对节点v的影响程度，这里用概率表示，且满如果满足，其中w指的是N(v)中处于活跃状态的节点，则节点v由未激活状态观点。可以证明，当运行次数t≥时，所有的节点都将会处于同一个状态，即要么全部活ICMLTM模型则是两个最为经典的模型，它们在研究中使用的较为广泛，属根据已有的研究成果，知道最大化问题属于一个NP-hard问题，为了有效的解决这一问题，我令初始集合B=遍历网络中的节点，选择一个节点使得σ(B∪{})–σ(B)取得最大值，即在集合B的基础令B=B∪{2，3其中，B表示已选出的最大化问题的节点结果的集合，σ表示节点集的收益，通常情况下是而上面提到的SI,SIS,SIR,ICM,LTM等模型大多都使用了这种贪心策略来解决复杂网络中的最大化这一问题。而为了尽量的减小系统的开销，人们往往会对已有的模型做出一定的改进来提高效率。的贪心算法CGA来选择出这K个节点的集合。他巧妙的发现了不同社团间的往往存在较少的联系，因此不在[4]中，作者将ICM模型的限制在任意节点v只有在它与初始集合的最短路径p和p+1步时才可中，作者在经典的模型中通过引入了连续时间马尔可夫链，从而提出了拓展的模型CTMC-ICM，最后，在CTMC-ICM的基础上，提出了新的节点度量SpreadRank及其算法描述，同样也取得了不错的效果。然而在[7]中，作者则在传统的SIS模型中引入了物理学中的渗流思想，通过将SIS模型与渗流模型的结合，来达到模拟的过程，其最终生成的示意图如下图所示，并且也取得了一定的分层图的渗流示意UM或者TMM以此达到比不错的行计算效如在8中作者在M模的基础过改了计算每个节收益的式来达提高并效率的虽然他依然用了心策略解决最大问题。但由于他这方式特适合多U的计算，因也取得不错的果。而在9中，作过先将复杂网络划出几个社，再在每社团中并计算寻找较大的节，以此来出最终的最大的节点集，也在保证结果正确的基础上一定程度的提高了运算的速度。在10]中，作者通过随机的选取边获得了一个DA通观察发每个节点仅仅与它子节点数有因此为可以过自向上的遍历这个DAG来获最终的。其他学领域交融合以来解决现实问题引起了们的广如病间关分析疾病与、蛋白之间的系等等。疾病模型，沙堆模型等，它们可能在一定的程度上限制了该领域的发展。而在现实中，这一模型的建立往往需要物理学家的努力。因此，不应该局限于自己的领域，也应关注一些相关领域的进展。而且由于多核CPU的飞速发展，如何有效的利用多核的优势来解决最大化这一问题也变的切实可问题也对提出了不小的 Kempe,D.,Kleinberg,J.,andTardos,E.,izingthespreadofinfluencethroughasocialnetwork, EyalEven-Dar,AsafShapira.Anote izingthespreadofinfluenceinsocial YuWang,GaoCong.GuojieSong,Kunqing munity-basedGreeedyAlgorithmforMiningTop-KInfluentialNodesinMobileSocialNetworks.2010. MasahiroKimura1andKazumiSaitoTarctableModelsforInformationDiffusioninSocial XiaohangZhang,JiZhu,QiWang,HanZhao.Identifyinginfluentialnodesincomplexnetworkswithcommunitystructure.2013 TianZhu,Bai izingthespreadofinfluencerankinginsocial KazumiSaito.Masahiro.EfficientdiscoveryofinfluentialnodesforSISmodelsinsocial JinhaKim,Seung-KeolKim,HwanjoYu.ScalableandParallelizableProcessingofInfluence izationforLarge-ScaleSocialNetworks.2013 GuojieSong,XiabingZhou,YuWang,andKunqingXie.InfluenceizationonLarge-ScaleMobileSocialNetwork:ADivide-and-ConquerMethod.2015［10］XiaodongLiu,MoLi.IMGPU:GcceleratedInfluenceizationinLarge-ScaleSocialAsurveyofstatusofinfluenceizationincomplexShi:Theinfluence izationproblemaimstofindtop-Kinfluentialindividualstoizetheinfluenceinasocialnetworkorotherscomplexnetwork.Ontheonehand,theizationproblemprovestobeaNP-hard,andontheotherhand,therearemanynodesinthenetworkandwealwaysfindthetop-Knodesintime.Soweusuallyusethegreedyalgorithmstosolvetheproblemnow.AsaresultofMulti-coreCPUbooming,whetherdesigningaparallelismalgor