科学网 › 标签 › 随机网络

标签: 随机网络

相关帖子	版块	作者	回复/查看	最后发表

没有相关内容

相关日志

行为在高聚类网络中传播更快: 热度 4 jalu 2010-12-21 10:31; 行为在高聚类网络中传播更快最近读了《 SCIENCE 》 2010 年 9 月 3 日 329 期的文章《 The Spread of Behavior in an Online Social Network Experiment 》，作者是美国麻省理工学院的经济社会学家 Damon Centola 。作者在线社会网络的行为传播实验是这样进行的。他邀请了 1540 名完全是出于兴趣的志愿者，随机地将他们一对一地分派到两个网络的节点上，一个是具有小世界特性的随机网络，另一个是高聚类的规则网络（ clustered-lattice network ），这两个网络的每一个节点的度都为 6 ，网络的拓扑结构在整个实验中是保持不变的。开始从这两个网络分别随机选一个节点（志愿者）作为起点，向这两个点的连接点（邻居， health buddies ）发去 email ，邀请他们到某个指定的健康论坛注册，如果他们到这个论坛注册就表示他们养成这种行为，那么系统再给他们的邻居发邮件邀请他们也去论坛注册（对于个人有可能被多次邀请），进而让活动继续下去。整个过程中确保匿名，志愿者之间彼此并不认识。作者对每个参与者创建匿名的个人在线信息，经过几周的实验，所有的数据作者都记录下来，然后分析在两种不同网络下行为的传播规律。我们知道，随机网络具有小的平均距离（有长程捷径的存在），但是它的聚类系数很小，而高聚类的规则网络有很高的聚类系数（每个节点的连接节点之间相互连接的概率很高），但是它的平均距离很大（没有长程捷径）。按照过去人们对于信息和疾病传播的认识，小世界网络中信息和疾病的传播速度快、传播范围广，而规则网络由于直径大传播速度慢。但是作者的实验结果恰恰相反，令人惊讶。作者对这两个网络分别独立进行 6 次实验（ 1 次节点数 N=98, 度 Z=6 ； 3 次 N=128, Z=6 ； 2 次 N=144, Z=8 ），共 12 个独立的行为传播实验。发现具小世界特征的随机网络的传播速度远不如规则网络的传播速度快，传播范围也没有后者大。在相同时间内，高聚类、大直径的规则网络的传播范围（ 53.77 ％）比小世界网络（ 38.26% ）传播范围大；规则网络上行为传播的速度（ 0.2820 10^-3 nodes/s) 比小世界网络上行为传播的速度（ 0.0643 10^-3 nodes/s ）快得多。可见，增加冗余信号 (email) 可以提高个体养成行为 ( 去健康论坛注册 ) 的可能性。再分析收到不同次数（ 1 ， 2 ， 3 ， 4 次） email 的节点愿意去健康论坛注册的比例，明显地收到次数越多行为形成的可能性就越高，但是相对增量量是减小的，超过 2 次 email 对行为形成的影响不再明显。最后再分析干预和强化对养成行为后的巩固（回访健康论坛）有多大的影响，收到 1 次 email 就去注册的群体中，大约 87 ％的节点在注册后就不回访， 11 ％的节点在注册后回访 1 次， 2 ％的节点在注册后回访 2 次；收到 2 次 email 就去注册的群体中，大约 67 ％的节点在注册后就不回访， 22 ％的节点在注册后回访 1 次， 11 ％的节点在注册后回访 2 次；收到 3 次 email 就去注册的群体中，大约 60 ％的节点在注册后就不回访， 21 ％的节点在注册后回访 1 次， 9 ％的节点在注册后回访 2 次；依次计算收到 4 次、 5 次 email 就去注册的群体中回访次数。说明干预和强化对养成行为后的巩固有着非常重要的作用。这一研究最重要的发现是：对于行为方式的传播与信息和疾病传播是不一样的。小世界网络中由于长程捷径的存在使得信息和疾病传播比较快，而行为方式的传播恰恰相反，它在高聚类网络比小世界网络中传播得更快更广。像聚类网络这样具有很多冗余的连接的拓扑结构，更有利于社会性的强化和社会行为的传播和巩固。我们是否可以说，网络的传播分为两种，一种是简单的接触型的传播，像一般的信息传播、 SARS 和禽流感的传播，在小世界网络中容易快速传播，所以阻止传播的方法主要是切断、隔离。在疫苗策略中提倡重点控制度大的具有长程边的活跃个体。网络的传播的另一种是多次强化型的传播，比如，行为的形成是非常复杂的，需要多次（社会性）的强化、干预、学习，行为形成的过程也比较慢些，它的传播不属于接触传播，所以像高聚类网络具有冗余连接结构，适合于形成行为的多次强化作用，就有利于行为的形成、传播和巩固。这一结论使我们更深入地理解网络传播动力学，根据不同的需要设计适应于不同传播的网络结构。文章也启发我们，为了健康行为的传播和巩固，要特别重视像社区、学校、公司、部队等（高聚类的）社团的工作，一个人在他（她）所在的集体中有广泛和频繁的联系，所以集体的良好风气和习惯对社团内的个体有重要的影响作用。对于行为传播这个问题，我认为还有进一步可以研究的问题。譬如这篇文章还没有考虑不同行为的形成需要干预强度的不同，某些行为的形成需要强干预，但也有的只需要弱干预就能形成，所以不同类型的行为很可能适合于不同结构的网络上传播。疾病传播中那些传播性不是很强的疾病，是否也需要考虑多次接触才感染的问题，即多次强化的因素？又譬如谣言的传播，谎言一百次成为真理，让人相信需要从不同方面多次接受消息，因此不同的网络适合于可信度不同的谣言的传播。另外，文章只考虑网络拓扑对行为传播动力学的影响，排除了其它因素，但是实际上人群都有人际关系，当考虑这些实际因素时，网络拓扑对行为传播的影响会发生什么样的改变呢？感谢博士生陈娟（目前在香港城市大学）和荷兰Groningen 大学刘慧博士，我们深入讨论过《 SCIENCE 》这篇文章。 The Spread of Behavior in an Online Social Network; 个人分类: 生活点滴|12108 次阅读|8 个评论

[转载]Google搜索与因特网的数学: 热度 1 wjc05 2010-1-25 19:33; http://www.casad.cas.cn/gzdt/200512/t20051206_43268.html 2005年12月3日下午，科学与中国院士专家巡讲团在南开大学伯苓楼一楼报告厅举办主题报告会，邀请中国科学院院士、第三世界科学院院士马志明研究员作题为Google搜索与因特网的数学的报告。此次报告会由南开大学副校长陈永川教授主持，近400名来自天津市各大高校的师生到场聆听了报告。马志明院士首先演示了Google可以在0.36秒内搜索出26,000项相关页面，而排在最前面的就是我们最感兴趣的。由此引申到报告的第一部分利用网络拓扑结构对网页进行排序。他说，实际上，我们的这个世界就是一个网络，因特网把我们的世界连成一体。Google搜索可以在极短的时间内把网页排序，根本原理就是利用网络的拓扑结构判断网页的重要性。马志明院士用一个形象的比喻来解释这一原理。在申请升职、提级的时候，或者申请博士答辩的时候，你会说你的文章多么重要，但是很可能评审专家们并不明白你的成果有多重要。现在流行的办法就是问你这些成果被引用的次数以及是否有国际权威引用，这两条往往是外行评价内行的一个办法。虽然这不应该是唯一的评价标准，但是在其他方法失效的情况下却是很有效的。Google在给出页面排序时也有两条标准，一是看有多少超级链接指向它；二是要看超级链接指向它的那个页面重要不重要。这两条直观的想法就是Google搜索的数学基础，是Google最基本的工作原理。马院士说，这样一个基本原理是和你们同年龄或者比你们年龄还小的两个年轻人发现的。1998年斯坦福大学的SergeyBrin和LarryPage想到了用上述原理刻画网页重要性，发表了一篇文章，并且把他们的算法取名叫做PageRank。这不仅是理论上的发现，文章发表之后他们就办公司实践了PageRank算法，并且非常成功。他们就是Google公司的创办人。马志明院士从图论的角度解释Google的排序原理：一是看这个页面对应顶点的度；二是要给连在这个顶点上的边一个权重，表明这个超级链接的重要性。具体的讲就是把所有的页面看作图里面的点，然后给每一个页面一个数量，用这个数量来刻画页面的重要性，这样网页的重要性就脱离了它的具体内容。我们只需从网络拓扑结构出发研究网页的重要性，最后转变为求有向图关联矩阵的非负特征向量，这样就可以用矩阵论来研究随机复杂网络。图论里面的这么一点知识解决了这样一个大的问题。而且按照这个原理对网页排序具有三个特点：第一，排序与问讯的问题无关；第二，排序与网页的内容无关；第三，只需要知道网页的图的结构。马志明院士指出，现在不同的公司包括微软研究院，Google公司，因特尔公司等都在相互竞争，都在研究怎样淘汰大量的垃圾页面，提高网页搜索的质量。然而，提高网页搜索质量的关键是算法的收敛速度。我的一位博士后用马氏链的办法解决了WWW2005一篇文章中关于算法收敛速度的猜想，而且证明的结论比这个猜想还广，可见数学真的很有实际意义。他说，随机复杂网络虽然是在经典图论的基础上发展起来的，但是它们之间存在很大的差别。复杂网络和图的不同之处在于网络是动态的、随机的，结点是大量的。在图论里面，我们可以问去掉哪几个点这个图就不连通了。对于随机复杂网络，我们要的是去掉百分之几的点网络就不工作了。网路和图，在我们日常生活中到处都有。例如信息网络：WWW,Internet，计算机共享，Email网,专利使用；技术网络：电力网，电话线路网；交通运输网：航线网，铁路网，公路网，自然河流网；社会网：演员合作网，友谊网，论文引用；姻亲关系网，科研合作网；生物网：食物链网，神经网，新陈代谢网，蛋白质网，基因网络等等都是随机复杂网络。这些领域相差甚远，但是人们发现，它们形成的随机复杂网络具有惊人的相同的统计特征：第一，小事件现象：网络中任意两点间距离的平均值很小；第二，聚集现象：网络中有足够多的三角形；第三，无标度现象：顶点的度的分布满足Scalingfree规律。马志明院士报告的第二部分讨论了因特网上病毒传播的阈值问题。他说，传统的疾病传播，把人和人之间的接触看作是等概率的，人跟人接触之后被传染的机会也是等概率的，这样所有的疾病都有一个传播的临界值。而一些统计物理学家证明，因特网上只要出现病毒，哪怕出现的概率很小，也会传播开来，也就是说网络上病毒的传播阈值是零。用随机复杂网络研究疾病预防会节约很多成本。预防疾病传统的方法是随机挑选百分之几的人打预防针，但是这不是最好的方法。随机选点将所有的结点平均化了，然而实际上有些结点的度数很高。接触传染的疾病预防应该基于网络模型，根据网络不均匀、不对称的分布特点，预防疾病较有效的方法是随机选取边，按照边来选择预防对象，这样可以最快的找到度数高的节点，并且可以节省很多人力和物力。例如对艾滋病的预防，非洲有些地方就是这么做的，效率非常高。在报告内容的第三部分，马志明院士介绍了随机复杂网络的研究现状。他说，目前人们在社会网络或计算机网络上传染过程、网络顶点故障对通讯网络性能的影响、网络相变与网络动态系统、蛋白质基因的网络结构等方面已经有了一些初步的研究。虽然，现在关于随机复杂网络的研究仍处于初级阶段，至今还没有成熟的理论框架和系统的程序和方法来研究复杂网络，甚至关于随机复杂网络的哪些属性属于最重要的研究目标这样一个基本问题都没有清楚的答案。但是，随机复杂网络蕴涵了很多深刻、有趣的数学难题，这些正吸引着国际一流的科学家。近年来Science,Nature,PhysicsRev.Letter等杂志上发表了大量研究和探讨复杂网络的文章。随机复杂网络的研究是一大片没有开垦的土地，在这里面有大量的工作值得我们去投入。最后，马志明院士总结道，现在网络的影响已经遍及世界的各个角落，研究随机复杂网络对社会发展具有战略意义，而数学正是研究它的有力、高效的工具。今后，我们需要继续研究发生在网络上的各种过程行为及其应用。随机复杂网络与自然科学、社会科学相互交叉融合，具有巨大的理论和应用前景。如果大量的老师和同学参与进来，就可能会做出开创性的工作。随机复杂网络是一个真正的交叉学科，它将成为跨学科研究的生长点，它的发展和广泛运用，都将有力地推动学科间的整合和交叉学科的诞生与繁荣。马志明院士生动精彩、内涵丰富、深入浅出、高瞻远瞩的报告激起了广大师生的强烈反响，受到了与会者的广泛好评。报告的同时，南开BBS上还进行着现场报道，共发消息30余篇，引发了同学们的热烈讨论。随着报告的结束，进入现场提问环节。来自天津市各大高校的数学学院、计算机学院、物理学院等不同专业的青年学子纷纷举手踊跃提问，马志明院士一一给予耐心、详细的解答。马志明院士深厚渊博的学识、精彩丰富的演讲和新颖独到的见解博得了与会师生热烈的掌声。 Google搜索与 Inter网的信息检索; 个人分类: 复杂网络|3981 次阅读|2 个评论

更多...

帐号		自动登录	找回密码
密码			注册

关闭 安全验证

标签: 随机网络

相关帖子

相关日志

关闭安全验证