Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ａｐｐｌｉｃａｔｉｏｎｓ ＩＳＳＮ １００１．９０８１ ２０１３．Ｏ１—０１ 计算机应用，２０１３，３３（１）：１０５—１０７，１１１ 文章编号：１００１—９０８１（２０１３）０１—０１０５—０３ ＣＯＤＥＮ ＪＹＩＩＤＵ ｈｔｔｐ：／／ｗｗｗ．ｊｏｃａ．ａｎ ｄｏｉ：１０．３７２４／ＳＰ．Ｊ．１０８７．２０１３．００１０５ 在线社交网络中信息传播模式的特征分析 韩 佳 ，肖如良 ，胡 耀 ，唐 涛 ，房丽娜 （１．福建师范大学软件学院，福州３５０１０８； ２．深圳信息职业技术学院软件学院，广东深圳５１８１７２） （ 通信作者电子邮箱ｘｉａｏｒｕｌｉａｎｇ＠１６３．ｃｏｍ） 摘要：在线社交网络以其独特的传播优势，已成为一种流行的社交媒体平台。针对在线社交网络中信息传播 模式的形式特点，结合传染病动力学原理，提出了在线社交网络中的信息传播模型。模型考虑了不同用户行为对传 播机理的影响，并建立了不同用户节点的演化方程组，模拟了信息传播的过程，分析了不同类型的用户在网络中的行 为特征以及影响信息传播的主要因素。实验结果表明：不同类型的用户在信息传播过程中有着特定的行为规律，信 息不会无地传播，并在最终达到平稳状态，并且传播系数和免疫系数越大，信息传播达到稳态的速度就越快。 关键词：在线社交网络；信息传播；传播模式；特征分析 中图分类号：ＴＰ３１１．１ 文献标志码：Ａ Ｃｈａｒａｃｔｅｒｉｓｔｉｃ ａｎａｌｙｓｉｓ ｏｆ ｉｎｆｏｒｍａｔｉｏｎ ｐｒｏｐａｇａｔｉｏｎ ｐａｔｔｅｒｎ ｉｎ ｏｎｌｉｎｅ ｓｏｃｉａｌ ｎｅｔｗｏｒｋ ＨＡＮ Ｊｉａ ，ＸＩＡＯ Ｒｕｌｉａｎｇ ，ＨＵ Ｙａｏ ，ＴＡＮＧ Ｔａｏ ，ＦＡＮＧ Ｌｉｎａ （１．Ｆａｃｕｌｔｙ ｏｆＳｏｔｗａｒｆｅ，ＦｕｉａｎＮｏｒｆｍａｌ Ｕｎｉｖｅｒｓｉｔｙ，Ｆｕｚｈｏｕ Ｆｕｊｉａｎ ３５０１０８，Ｃｈｉｎａ； ２．Ｄｅｐａｒｔｍｅｎｔ ｏｆＳｏｔｗａｒｆｅ，Ｓｈｅｎｚｈｅｎ Ｉｎｓｔｉｔｕｔｅ ｏｆＩｎｆｏｒｍａｔｉｏｎ Ｔｅｃｈｎｏｌｏｇｙ，Ｓｈｅｎｚｈｅｎ Ｇｕａｎｇｄｏｎｇ ５１８１７２，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｂｅｃａｕｓｅ ｏｆ ｉｔｓ ｕｎｉｑｕｅ ａｄｖａｎｔａｇｅ ｏｆ ｉｎｆｏｒｍａｔｉｏｎ ｐｒｏｐａｇａｔｉｏｎ，ｔｈｅ ｏｎｌｉｎｅ ｓｏｃｉａｌ ｎｅｔｗｏｒｋ ｈａｓ ｂｅｅｎ ａ ｐｏｐｕｌａｒ ｓｏｃｉａｌ ｃｏｍｍｕｎｉｃａｔｉｏｎ ｐｌａｔｆｏｒｍ． Ｉｎ ｖｉｅｗ ｏｆ ｔｈｅ ｃｈａｒａｃｔｅｒｉｓｔｉｃｓ ｏｆ ｔｈｅ ｆｏｒｍ ｏｆ ｉｆｏｒｎｍａｔｉｏｎ ｐｒｏｐａｇａｔｉｏｎ ａｎｄ ｔｈｅ ｄｙｎａｍｉｃｓ ｔｈｅｏｒｙ ｏｆ ｉｎｆｅｃｔｉｏｕｓ ｄｉｓｅａｓｅｓ，ｔｈｉｓ ｐａｐｅｒ ｐｕｔ ｆｏｒｗａｒｄ ｔｈｅ ｍｏｄｅｌ ｏｆ ｉｎｆｏｒｍａｔｉｏｎ ｐｒｏｐａｇａｔｉｏｎ ｔｈｒｏｕｇｈ ｏｎｌｉｎｅ ｓｏｃｉａｌ ｎｅｔｗｏｒｋ．Ｔｈｅ ｍｏｄｅｌ ｃｏｎｓｉｄｅｒｅｄ ｔｈｅ ｉｎｆｌｕｅｎｃｅ ｏｆ ｄｉｆｆｅｒｅｎｔ ｕｓｅｒｓ’ｂｅｈａｖｉｏｒｓ ｏｎ ｔｈｅ ｔｒａｎｓｍｉｓｓｉｏｎ ｍｅｃｈａｎｉｓｍ，ｓｅｔ ｕｐ ｔｈｅ ｅｖｏｌｕｔｉｏｎ ｅｑｕａｔｉｏｎｓ ｏｆ ｄｉｆｆｅｒｅｎｔ ｕｓｅｒ ｎｏｄｅｓ，ｓｉｍｕｌａｔｅｄ ｔｈｅ ｐｒｏｃｅｓｓ ｏｆ ｉｆｏｒｎｍａｔｉｏｎ ｐｒｏｐａｇａｔｉｏｎ，ａｎｄ ａｎａｌｙｚｅｄ ｔｈｅ ｂｅｈａｖｉｏｒ ｃｈａｒａｃｔｅｒｉｓｔｉｃｓ ｏｆ ｔｈｅ ｄｉｆｆｅｒｅｎｔ ｔｙｐｅｓ ｏｆ ｕｓｅｒｓ ａｎｄ ｍａｉｎ ｆａｃｔｏｒｓ ｔｈａｔ ｉｎｆｌｕｅｎｃｅｄ ｔｈｅ ｉｆｏｒｎｍａｔｉｏｎ ｐｒｏｐａｇａｔｉｏｎ．Ｔｈｅ ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｓｈｏｗ ｔｈａｔ ｄｉｆｆｅｒｅｎｔ ｔｙｐｅｓ ｏｆ ｕｓｅｒｓ ｈａｖｅ ｓｐｅｃｉｌ ｂｅｈａｖｉｏｒ ｒｕｌｅｓ ｉｎ ｔｈｅ ｐｒｏｃｅｓｓ ｏｆ ｉａｆｏｒｎｍａｔｉｏｎ ｐｒｏｐａｇａｔｉｏｎ，ｉ．ｅ．，ｉｎｆｏｒｍａｔｉｏｎ ｃａｎｎｏｔ ｂｅ ｔｒａｎｓｐｏｒｔｅｄ ｅｎｄｌｅｓｓｌｙ，ａｎｄ ｂｅ ｒｅａｃｈｅｄ ａｔ ａ ｓｔａｔｉｏｎａｒｙ ｓｔａｔｅ，ａｎｄ ｔｈｅ ｌａｒｇｅｒ ｔｈｅ ｓｐｒｅａｄ ｃｏｅｆｉｃｉｆｅｎｔ ｏｒ ｉｍｍｕｎｅ ｃｏｅｆｉｃｉｆｅｎｔ ｉｓ，ｔｈｅ ｆａｓｔｅｒ ｉｔ ｒｅａｃｈｅｄ ｔｈｅ ｓｔａｔｉｏｎａｒｙ ｓｔａｔｅ． Ｋｅｙ ｗｏｒｄｓ：ｏｎｌｉｎｅ ｓｏｃｉａｌ ｎｅｔｗｏｒｋ；ｉｆｏｒｍａｔｉｎｏｎ ｐｒｏｐａｇａｔｉｏｎ；ｔｒａｎｓｍｉｓｓｉｏｎ ｐａｔｔｅｒｎ；ｃｈａｒａｃｔｅｒｉｓｔｉｃ ａｎａｌｙｓｉｓ ０ 引言 近年来社交网络得到了迅猛的发展，人们对信息的获取 和消息的传递开始变得越来越依赖于网络，如国外的 Ｆａｃｅｂｏｏｋ 、ＭｙＳｐａｃｅ 等，国内的人人网 、开心网 等。用 是由度数大的节点创建的。总之，尽管在线社交网络问题已 经有了大量的研究成果，但仍需要进一步的研究来揭示以人 为主体的在线社交网络中信息的传播机制。 在线社交网络与传统的Ｗｅｂ网络最大的不同之处在于： 传统的Ｗｅｂ网络的主体是内容信息，依靠内容信息组织在一 起，呈现给用户；而社交网络的主体是人，依靠人与人之间的 朋友关系组织在一起。在线社交网络必须具备有３项基本功 户可以通过分享新闻、日志、视频、音乐及相片等方法，维持和 开拓人际关系。作为一种流行的社交媒体平台，社交网络已 经成为在线社交网络，正以前所未有的传播优势和巨大影响 力，成为拥有强大社会影响力和动员力的重要传播工具。 在线社交网络是一个复杂的虚拟社会，人们在现实生活 能，即允许用户：１）创建和维护朋友关系；２）上传自己预分享 的内容信息；３）浏览其他用户分享的内容信息并能进行评 论、分享、转发等操作。基于这些用户所能拥有的功能，人与 人之间的关系开始向“虚拟化”转变，而这种“虚拟化”的关系 又对人与人之间的关系产生着一定的影响。如何去描述在线 中的行为和他们在社交网络中的行为有很大程度的相似性， 分析社交网络中的用户行为和社交网络的结构性质等已经成 为学者们研究的热点问题。例如，文献［５—６］研究了在线社 交网络的网络拓补结构的演化特性以及度分布、聚类系数、簇 系数、顶点的度相关性等社交网络的相关属性；文献［７—９］ 从用户点击网站、用户群以及影响最大化等角度，对信息产生 和扩散中的用户行为进行了研究；文献［１０］从网络安全和隐 社交网络中的信息传播模式，揭示其传播特性，对以网络为主 体的社会来说，具有重要的理论和应用价值。以前人们大都 是在规则网络的基础上研究信息的传播方式，但是鉴于在线 社交网络所具有的网状式的结构特征，在线社交网络中信息 的传播行为与规则网络相比有着本质上的区别。本文针对该 问题，利用传染病动力学模型，对在线社交网络中信息传播模 式进行了理论建模和仿真分析，有助于更深刻地理解在线社 交网络中的信息传播模式及其特征，也对研究网络传播 私保护的角度，对几个大型的社交网络进行了分析；Ｍｉｓｌｏｖｅ 等… 通过收集Ｆｌｉｃｋｒ网络的数据生长来研究在线社交网络 中用户的行为模式，结果发现社交网络中信息传播的新路径 收稿日期：２０１２—０７．０４：修回日期：２０１２—０８一Ｏ９。 基金项目：教育部规划基金资助项目（１１ＹＪＡ８６００２８）；福建省科技计划重大项目（２０１１Ｈ６００６）。 作者简介：韩佳（１９８７一），女，湖北天门人，硕士研究生，主要研究方向：社交网络、软件工程； 肖如良（１９６６一），男，湖南娄底人，教授，博士 ＣＣＦ高级会员，主要研究方向：社交网络、虚拟化、软件工程ｉ胡耀（１９８７一），男，湖南永州人，硕士研究生，主要研究方向：社交网络、虚拟化。 １０６ 计算机应用 第３３卷 等有一定的价值。 １ 在线社交网络的信息传播特征 相比于传统的Ｗｅｂ网，在线社交网络不仅提供信息供用 户使用，而且允许用户彼此之间进行交流，是提供信息共享的 平台，并且信息更新速度快，数据量大。在线社交网络中，一 个用户发出的信息会在其朋友的个人界面展示，其好友可能 会以一定的概率传播该信息，也可能只是纯粹地浏览信息。 也就是说 ，若该用户的好友对该信息感兴趣则可能传播信 息；若其好友对该信息内容不感兴趣，则不会传播该信息而成 为免疫者。 举个例子来说，在某个时刻用户Ａ在自己好友动态中看 到了用户Ｂ的动态更新，那么用户Ａ可能对其进行分享或转 发，这一行为就会出现在用户Ａ的朋友的好友动态中，用户Ａ 的朋友就能见到这些消息；若是用户Ａ对用户Ｂ发出的信息 不感兴趣而不作出任何回应，那么用户Ａ的朋友就见不到这 条消息，那么通过用户Ａ的消息链就可能被迫中断。接下 来，用户Ａ的朋友，用户Ａ的朋友的朋友都可能有相似于用 户Ａ的操作。此外，用户Ｂ可能不止有用户Ａ一个朋友，其 他的朋友也会有类似Ａ的行为，依此类推，信息就以网状的 形式像四周扩散开来。信息传播模式如图１所示。 ＠ ③ ④⑤⑥④＠＿＠ ⑦＠＠⑦＠② （ａ）信息传播演化形式 （ｂ）整体信息传播链 图１信息传播模式 当一个用户发出消息后，与它相连的所有朋友用户都有 可能以一定的概率分享转发消息，或浏览信息而不进行操作。 图１中，若用户２与用户１和５之间有链接，则２发出的信息 Ｉ则会以一定的概率传递到１和５；而用户１又与用户４和用 户８之问有链接，用户５又与用户６和用户９之间有链接，则 信息Ｉ将有可能传递到用户４，６，８，９，而这些用户又会有他们 自己的朋友关系网，信息会通过这些朋友关系传递下去。 图１是在线社交网络中信息传播模式的简单描述。就某 一特定的消息来说，它是以信息源为中心向四周散射传播开 去的，信息的走向具有不规则性，只有对该信息感兴趣的用户 对信息进行分享、转发等，信息才会沿着这条信息链继续传 播；否则，通过这个用户的信息链将中断。 ２传染病传播的ＳＩＲ模型分析 在流行病传播的研究中，大多是基于ＳＩＲ（Ｓｕｓｃｅｐｔｉｂｌｅ— Ｉｎｆｅｃｔｉｏｕｓ—Ｒｅｍｏｖｅｄ）模型 。该模型将总人口分为以下三 类：易感者（ｓｕｓｃｅｐｔｉｂｌｅｓ），其数量记为Ｓ（ｔ），表示ｔ时刻未染 病但有可能被该类疾病传染的人数；染病者（ｉｎｆｅｃｔｉｖｅｓ），其 数量记为，（ｔ），表示ｔ时刻已被感染成为病人而且具有传染力 的人数；恢复者（ｒｅｃｏｖｅｒｅｄ），其数量记为Ｒ（ｔ），表示 时刻已 从染病者中移出的人数。设总人口为Ｎ（ｔ），则有Ｎ（ｆ）＝ Ｓ（ｔ）＋，（ ）＋Ｒ（ｔ）。 ＳＩＲ模型的建立基于以下３个假设。 １）不考虑人口的出生、死亡、流动等种群动力因素。人口 始终保持一个常数，即Ⅳ（ｔ）。 ２）一个病人一旦与易感者接触就必然具有一定的传染 力。假设￡时刻单位时间内，一个病人能传染的易感者数目与 此环境内易感者总数Ｓ（ｔ）成正比，比例系数为口，从而在ｔ时 刻单位时间内被所有病人传染的人数为 （ ），（ ）。 ３）ｔ时刻，单位时间内从染病者中移出的人数与病人数量 成正比，比例系数为 ，单位时间内移出者的数量为ＴＩ（ｔ）。因 此有式（１）： ｄｌ ｛ ＝一／３ｓＩ （１） ， 通过第１章的分析可知，社交网络中的信息传播是非线 性的动力学系统的一个例子，信息的这种传播行为和人群中 的流行病十分相似，因此，可以借助生物流行病领域已有的数 学方法来对在线社交网络中的信息传播进行研究。 但用来描述在线社交网络中的信息传播，ＳＩＲ模型则存 在着不足之处。ＳＩＲ模型认为某封闭群体中的３种状态ＳＩＲ随 时间ｔ的变化之和其自身及两个常量 ， 有关，而没有考虑到 其他因素的影响。在现实生活中，当流行病出现的时候人们往 往会采取一些措施如对居住的环境进行消毒或进行免疫接种 等，使自身从易感者向免疫者转变；在社交网络中，用户对信 息的兴趣度也可能随着时间的推移或周围环境的影响等发生 改变，易感染的用户也有可能直接转变为免疫者。因此，若单 纯地使用ＳＩＲ模型，则就成了一种很被动的信息传播方式。所 以要研究在线社交网络中的信息传播，必须在ＳＩＲ模型的基 础上进行改进。 ３ 基于ＳＩＲ的在线社交网络信息传播模型 本文将在线社交网络中的用户定义为节点，节点之间的 边表示用户的朋友关系，信息沿着边进行传播。根据在线社 交网络中信息的传播模式，将网络中的节点分为３类¨ １：传 播节点（Ｉ），未感染节点（ｓ）和免疫节点（Ｒ）。传播节点指该 节点能接受其邻居节点的信息，并具有传播该信息的能力；未 感染节点指该节点没有接受过来自其邻居节点的信息，但有 概率被感染；免疫节点指该节点能接受其邻居节点的信息，但 不具有传播能力。 在线社交网络中三类节点的态机制，如图２所示。 易感染节点Ｓ（ｔ） 自发转变 免疫节点Ｒ（ｔ） 接自 接触转 ＬＪＩ ！兰竺变 感染节点，（ 图２信息传播的状态机制 在线社交网络中信息传播的３种状态转变规则。 １）一个处于易感染状态的节点接触到感染节点时，易感 染节点可能以概率Ａ转变为感染节点，Ａ为传播系数。 ２）一个处于感染状态的节点与一个免疫节点接触时，传 播节点可能以概率 转变为免疫节点， 为免疫系数。 ３）随着时间的推移和周围环境的影响，处于易感染状态 的节点将会以概率 向免疫节点转变， 为自免疫系数；处于 感染状态的节点将会以概率６自动向免疫节点转变， 为自免 疫系数。 ４）感染节点的信息传播链会在一定时刻停止，即信息不 会无地传播。 显然，ｔ时刻，易感染节点的变化率除了与感染节点的传 播系数Ａ有关，还与其自身的免疫系数 有关；免疫节点的变 化率除了与感染节点的免疫系数 有关，还与易感染节点的 免疫系数 和感染节点的自发免疫系数６有关。用Ｒ （ｔ）和 Ｒ （ｔ）表示易感染节点和感染节点能够自发转变为免疫节点 的数量，则有式（２）： 第１期 韩佳等：在线社交网络中信息传播模式的特征分析 １０７ 系数不可忽略，但它们的变化范围很小，故在线社交网络中对 信息的传播起主要作用的是传播系数Ａ和免疫系数 。 ｌ塑 一 ＋垫 岛 趱 衄 由以上分析可知，Ｒ （ｔ）的变化率与易感染节点自发转 变的免疫系数 成正比； （ｔ）的变化率与感染节点自发转变 的免疫系数６和接触的免疫系数／ｘ之和成正比，因此有式 咖 ｆｄＲ，（ｔ） ＴＳ（ （３） 蛊 ｆ ＝一ＡＳ（ ㈩一ｙｓ㈩ ｛ ｄｌ（ｔ）＝ａｓ（ （ｆ）一（ ＋ ㈤ （４） 【ｄＲｄ（ｔｔ）・＝Ｔｓ（ ）＋（ ＋６），（ ） 其中Ａ， ， ，６均为正常数。Ａ， 为一般情况下的传播系数 和免疫系数； ，６为在环境影响下易感染节点和感染节点自 ４实验结果及分析 实验采用的数据是Ｅｐｍｉｏｎｓ．ｃｏｒｎ的ｗｈｏ—ｔｒｕｓｔ—ｗｈｏｍ在线 社交网络的真实数据集。该数据集的基本数据如下：节点总 数量为Ｎ＝７５ ８７９，节点之间边的数量为５０８ ８３７，平均度为 ６．７０５９，平均聚类系数为０．２２８ ３，最长的最短路径为ｌ３。该 网络初始度分布如图３所示。 图３网络初始度分布 设置初始状态网络中只有一个传播节点，其余节点全部 为未感染节点，即Ｉ（０）＝１《Ｎ，Ｒ（０）＝０，Ｓ（０）＝Ｎ一１，设 置模型参数：Ａ＝０．３， ：０．１，迭代次数Ｔ＝３００。 随着时间的推移和周围环境的影响，用户中的易感染节 点和感染节点用户能够自动转变为免疫节点用户，取 ＝占＝ ０．０１２５。这样即可求得，网络中传播节点、未感染节点和免疫 节点的数量所占节点总数的比例（分别用ｓ（ｔ），ｉ（ｔ），ｒ（ｔ）表 示）随着时间的演化情况，如图４所示。 从图４中可以看出：当ｔ趋向于无穷大时，信息的传播过 程将达到平稳状态，各类节点的数量所占的比例将不再发生 变化。传播节点所占的比例ｉ（ｔ）在初始阶段快速增长，当达 到最大值后迅速减小，直到趋向于零；未感染节点所占的比例 ｓ（￡）不断衰减直到趋向于零；免疫节点所占的比例ｒ（ ）在初 期呈现较快的增长趋势，在一定阶段后趋于平稳直到达到最 大值。 在信息传播趋于稳态时，网络中用户节点最终都将转变 为免疫状态Ｒ态。尽管易感染节点和感染节点用户的自免疫 臣 ｔ 图４三类节点所占比例随时问的变化关系 改变传播系数Ａ值，而其他参数保持不变时，Ｒ态节点所 占的比例随时问的变化情况如图５所示。 ｔ 图５ ｒ（ｔ）在Ａ取不同值的情况下随时间的变化关系 改变免疫系数 的值，而其他参数保持不变时，Ｒ态节点 所占的比例随时间的变化情况如图６所示。 ｔ 图６ ｒ（￡）在 取不同值的情况下随时间的变化关系 从图５～６中可以看出，当传播系数Ａ越大，ｒ（ｔ）增大得 越快，信息传播达到平稳状态的时间就越短；当传播系数Ａ很 小时，信息仍能在网络中传播，但该信息传播达到趋于平稳的 时间将会较长，即信息的传播具有一定的时延性。当免疫系数 逐渐增大时，ｒ（ｔ）也逐渐增大；当免疫系数 较小时，在信息 传播的初期，Ｒ态所占的比例增加得较为缓慢，经过一定阶段 将快速增长直至平稳状态。 ５ 结语 通过分析在线社交网络中信息传播模式的形式特点，结 合传染病动力学原理，在对ＳＩＲ模型改进的基础上，提出了在 线社交网络中的信息传播模型，并建立了微分方程组。仿真 分析了社交网络中的信息传播过程以及三种不同类型的用户 节点在信息传播中的行为规律，结果表明：信息不可能无 （下转第１１１页） 第１期 邓亚平等：基于控制的低能耗多跳分簇路由协议 ｅｔｙ，２０００：３００—３０４． ｌ１１ ［６］ ＭＡＮＪＥＳＨＷＡＲ Ａ，ＡＧＲＡＷＡＬ Ｄ．ＴＥＥＮ：ａ ｒｏｕｔｉｎｇ ｐｒｏｔｏｃｏｌ ｆｏｒ ｅｎｈ￣ｃｅｄ ｅｆｆｉｃｉｅｎｃｙ ｉｎ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ 意 焉 蓬 ｔｈｅ １５ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｐａｒｌｌａｅｌ ａｎｄ Ｄｉｓｔｉｒｂｕｔｅｄ Ｐｒｏｃｅｓｓ－ ｉｎｇ．Ｗａｓｈｉｎｇｔｏｎ，ＤＣ：ＩＥＥＥ Ｃｏｍｐｕｔｅｒ Ｓｏｃｉｅｔｙ，２００１：２００１—２０Ｏ９． 【７］ ＭＡＮＪＥＳＨＷＡＲ Ａ，ＡＧＡＲＷＡＬ Ｄ．ＡＰＴＥＥＮ：ａ ｈｙｂｒｉｄ ｐｒｏｔｏｃｏｌ ｆｏｒ ｅｆｆｉｃｉｅｎｔ ｒｏｕｔｉｎｇ ａｎｄ ｃｏｍｐｒｅｈｅｎｓｉｖｅ ｉｎｆｏｒｍａｔｉｏｎ ｒｅｔｉｅｖａｌｒ ｉｎ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ １６ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｐａｒａｌｌｅｌ ａｎｄ Ｄｉｓｔｉｒｂｕｔｅｄ Ｐｒｏｃｅｓｓｉｎｇ Ｓｙｍｐｏｓｉｕｍ．Ｗａｓｈｉｎｇｔｏｎ，ＤＣ：ＩＥＥＥ Ｃｏｍｐｕｔｅｒ Ｓｏｃｉｅｔｙ，２００２：１９５—２０２． ［８］ＨＥ Ｔ，ＳＴＡＮＫＯＶＩＣ Ｊ Ａ，ＬＵ Ｃ Ｙ，ｅｔ ａ１．ＳＰＥＥＤ：ａ ｓｔａｔｅｌｅｓｓ ｐｒｏｔｏ— 相对时间脾 ｃｏｌ ｆｏｒ ｒｅａｌ ｔｉｍｅ ｃｏｍｍｕｎｉｃａｔｉｏｎ ｉｎ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ［Ｃ］／／Ｐｒｏｃｅｅｄ— ｉｎｇｓ ｏｆ ｔｈｅ ２３ｒｄ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｄｉｓｔｉｂｕｔｒｅｄ Ｃｏｍｐｕｔｉｎｇ 图４网络总剩余能量图 Ｓｙｓｔｅｍ．Ｗａｓｈｉｎｇｔｏｎ，ＤＣ：ＩＥＥＥ Ｃｏｍｐｕｔｅｒ Ｓｏｃｉｅｔｙ，２００３：４６—５５． ４ 结语 ［９］ＬＩＮＤＳＥＹ Ｓ，ＲＡＧＨＡＶＥＮＤＲＡ Ｃ Ｓ．ＰＥＧＡＳＩＳ：ｐｏｗｅｒ ｅｆｆｉｃｉｅｎｔ 本文针对多跳分簇无线传感网中普遍问题与ＥＥＵＣ中的 ｇａｔｈｅｒｉｎｇ ｉｎ ｓｅｎｓｏｒ ｉｎｆｏｒｍａｔｉｏｎ ｓｙｓｔｅｍｓ［Ｃ】／／Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ 不足进行了深入分析，通过控制成簇大小与数量，建立能量高 ２００２ Ａｅｒｏｓｐａｃｅ Ｃｏｎｆｅｒｅｎｃｅ．Ｗａｓｈｉｎｇｔｏｎ，ＤＣ：ＩＥＥＥ Ｃｏｍｐｕｔｅｒ Ｓｏ－ ｃｉｅｔｙ，２００２：３－１ １２５—３－１ １３０． 效的多跳链路，利用将整个网络生命期划分为两部分实现减 【１０］ ＹＯＵＮＩＳ Ｏ，ＦＡＨＭＹ Ｓ．ＨＥＥＤ：ａ ｈｙｂｒｉｄ，ｅｎｅｒｇｙ－ｅｆｆｉｃｉｅｎｔ，ｄｉｓ— 少成簇和建立多跳链路的次数，弥补了ＥＥＵＣ中的不足，有效 ｔｒｉｂｕｔｅｄ ｃｌｕｓｔｅｒｉｎｇ ａｐｐｒｏａｃｈ ｆｏｒ Ａｄ Ｈｏｃ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ［Ｊ］．ＩＥＥＥ 地降低了网络总能耗。仿真结果表明，与ＬＥＡＣＨ和ＥＥＵＣ算 Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｍｏｂｉｌｅ Ｃｏｍｐｕｔｉｎｇ，２００４，３（４）：３６６—３７９． 法比较，ＣＬＭＰ算法减少了网络总能耗，使负载更均衡，延长 【１ １］ＬＯＳＣＲＩ Ｖ，ＭＯＲＡＢＩＴＯ Ｇ，ＭＡＲＡＮＯ Ｓ．Ａ ｔｗｏ ｌｅｖｅｌ ｈｉｅｒｒａｃｈｙ 了网络生命期。 ｏｆｒ ｌｏｗ ｅｎｅｒｇｙ ａｄａｐｔｉｖｅ ｃｌｕｓｔｅｒｉｎｇ ｈｉｅｒａｒｃｈｙ（ＴＬ—ＬＥＡＣＨ）［Ｃ］／／ 参考文献： Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ６２ｎｄ ＩＥＥＥ Ｖｅｈｉｃｕｌｒａ Ｔｅｃｈｎｏｌｏｇｙ Ｃｏｎｆｅｒｅｎｃｅ． 【１］ 李利民，李建中，陈渝．无线传感器网络［Ｍ］．北京：清华大学出 Ｗａｓｈｉｎｇｔｏｎ．ＤＣ：ＩＥＥＥ Ｃｏｍｐｕｔｅｒ Ｓｏｃｉｅｔｙ．２００５：１８０９—１８１３． 版社，２００５． ［１２］ ＳＯＲＯ Ｓ，ＨＥＩＮＺＥＬＭＡＮ Ｗ Ｂ．Ｐｒｏｌｏｎｇｉｎｇ ｔｈｅ ｌｉｆｅｔｉｍｅ ｏｆ ｗｉｒｅｌｅｓｓ ［２１ 沈波，张世永，钟亦平．无线传感器网络分簇路由协议［Ｊ１．软件 ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ ｖｉａ ｕｎｅｑｕａｌ ｃｌｕｓｔｅｒｉｎｇ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ 学报，２００６，１７（７）：１５８８—１６００． １９ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｐａｒａｌｌｅｌ ａｎｄ Ｄｉｓｔｒｉｂｕｔｅｄ Ｐｒｏｃｅｓｓｉｎｇ Ｓｙｍｐｏｓｉｕｍ． ［３】余勇昌，韦岗．无线传感器网络中基于ＰＥＧＡＳＩＳ协议的改进算 Ｗａｓｈｉｎｇｔｏｎ，ＤＣ：ＩＥＥＥ Ｃｏｍｐｕｔｅｒ Ｓｏｃｉｅｔｙ，２００５：８—１５． 法【Ｊ］．电子学报，２００８，３６（７）：１３０９—１３１３． ［１３］ ＹＥ Ｍ，ＬＩ Ｃ，ＣＨＥＮ Ｇ，ｅｔ ａ１．ＥＥＣＳ：ａｎ ｅｎｅｒｇｙ ｅｆｉｆｃｉｅｎｔ ｃｌｕｓｔｅ— ［４］ ＭＨＡＴＲＥ Ｖ，ＲＯＳＥＮＢＥＲＧ Ｃ．Ｄｅｓｉｇｎ ｇｕｉｄｅｌｉｎｅｓ ｆｏｒ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｉｒｎｇ ｓｃｈｅｍｅ ｉｎ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ｎｅｔｗｏｒｋ：ｃｏｍｍｕｎｉｃａｔｉｏｎ，ｃｌｕｓｔｅｒｉｎｇ ａｎｄ ａｇｇｒｅｇａｔｉｏｎ【Ｊ】．Ａｄ Ｈｏｃ ２４ｔｈ ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｐｅｒｆｏｒｍａｎｃｅ，Ｃｏｍｐｕｔｉｎｇ Ｎｅｔｗｏｒｋｓ，２００４，２（１）：４５—６３． ａｎｄ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ．Ｐｉｓｅａｔａｗａｙ：ＩＥＥＥ Ｐｒｅｓｓ，２００５：５３５—５４０． 【５］ＨＥＩＮＺＥＬＭＡＮ Ｗ Ｒ，ＣＨＡＮＤＲＡＫＡＳＡＮ Ａ，ＢＡＬＡＬＣＲＩＳＨＮＡＮ ［１４］ 李法成，陈贵海，叶懋，等．一种基于非均匀分簇的无线传感器 Ｈ．Ｅｎｅｒｇｙ ｅｆｉｆｃｉｅｎｔ ｃｏｍｍｕｎｉｃａｔｉｏｎ ｐｒｏｔｏｃｏｌ ｆｏｒ ｗｉｒｅｌｅｓｓ ｍｉｃｒｏｓｅｎｓｏｒ 网络路由协议［Ｊ】ｌ计算机学报，２００７，３０（１）：２７—３６． ｎｅｔｗｏｒｋｓ［Ｃ】／／Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ３３ｒｄ Ｈａｗａｉｉ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎ． ［１５］ 施叶玲，陈彬兵．无线传感器网络改进的ＬＥＡＣＨ・ＩＤ算法［Ｊ】． ｆｅｒｅｎｅｅ ｏｎ Ｓｙｓｔｅｍ Ｓｃｉｅｎｃｅ．Ｗａｓｈｉｎｇｔｏｎ，ＤＣ：ＩＥＥＥ Ｃｏｍｐｕｔｅｒ Ｓｏｃｉ— 计算机应用，２０１１，３１（２）：３２４—３２７． （上接第１０７页） 地传播，当ｔ趋向于无穷大时，信息的传播过程将达到平稳状 Ｙｏｒｋ：ＡＣＭ Ｐｒｅｓｓ．２００７：２９—４２． 态，各类节点的数量将不再变化；当传播系数较小时，信息仍 ［７］ ＢＥＮＥＶＥＮＵＴ０ Ｆ，ＲＯＤＲＩＧＵＥＳ Ｔ．ＣＨＡ Ｍ．ｅｔ ａ１．Ｃｈａｒａｅｔｅｒｉｚｉｎｇ 能在网络中传播，并且传播系数和免疫系数的大小发生变化 ｕｓｅｒ ｂｅｈａｖｉｏｒ ｉｎ ｏｎｌｉｎｅ ｓｏｃｉａｌ ｎｅｔｗｏｒｋｓ『Ｃ１／／ＩＭＣ，０９：Ｐｒｏｃｅｅｄｉｎｇｓ 时，信息传播的快慢程度将发生相应的改变。本文有助于更 ｏｆ ｔｈｅ ９ｔｈ ＡＣＭ ＳＩＧＣＯＭＭ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｉｎｔｅｒｎｅｔ Ｍｅａｓｕｒｅｍｅｎｔ 深刻地理解在线社交网络中的信息传播行为和合理地引导网 Ｃｏｎｆｅｒｅｎｃｅ．Ｎｅｗ Ｙｏｒｋ：ＡＣＭ Ｐｒｅｓｓ．２００９：４９—６２． 络。下一阶段的任务将是研究动态网络中，具有不同度 ［８】 ＣＨＥＮ Ｗ，ＷＡＮＧ Ｙ Ｊ．ＹＡＮＧ Ｓ Ｙ．Ｅｆｉｆｃｉｅｎｔ ｉｎｆｌｕｅｎｃｅ ｎｍｘｉｍｉｚａ— ｔｉｏｎ ｉｎ ｓｏｃｉａｌ ｎｅｔｗｏｒｋｓ ｆ Ｃ １／／ＫＤＤ，ｏ９：Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ １５ｔｈ 的用户节点对信息传播产生的影响。 ＡＣＭ ＳＩＧＫＤＤ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｋｎｏｗｌｅｄｇｅ Ｄｉｓｃｏｖｅｒｙ ａｎｄ 参考文献： Ｄａｔａ Ｍｉｎｉｎｇ．Ｎｅｗ Ｙｏｒｋ：ＡＣＭ Ｐｒｅｓｓ．２００９：１９９—２０８． 【１］ Ｆａｅｅｂｏｏｋ［ＥＢ／ＯＬ］． ［２０１２—０３—１２］．ｈｔｔｐ：／／ｗｗｗ．ｆａｃｅｂｏｏｋ． 【９］ ＳＨＩ Ｘ Ｌ，ＺＨＵ Ｊ，ＣＡＩ Ｒ，ｅｔ ａ１．Ｕｓｅｒ ｇｒｏｕｐｉｎｇ ｂｅｈａｖｉｏｒ ｉｎ ｏｎｌｉｎｅ ｃｏｒｎ／． ｆｏｒｕｍｓ ｆ Ｃ］／／ＫＤＤ’０９：Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ １５ｔｈ ＡＣＭ Ｓ１ＧＫＤＤ Ｉｎ． ［２］ ＭｙＳｐａｃｅ［ＥＢ／ＯＬ］． ［２０１２－０３—１２］．ｈｔｔｐ：／／ｗｗｗ．ｍｙｓｐａｃｅ． ｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｅｅ ｏｎ Ｋｎｏｗｌｅｄｇｅ Ｄｉｓｃｏｖｅｒｙ ａｎｄ Ｄａｔａ Ｍｉｎｉｎｇ． ｃｏｒｎ／． Ｎｅｗ Ｙｏｒｋ：ＡＣＭ Ｐｒｅｓｓ．２００９：７７７—７８６． ［３］人人网ｆＥＢ／ＯＬ］．［２０１２・０３－２５］．ｈｔｔｐ：／／ｗｗｗ．ｒｅｎｒｅｎ．ｃｏｒｎ／． ［１Ｏ］ 刘建伟，李为宇，孙钰．社交网络安全问题及其解决方案［Ｊ］．中 ［４】 开心网【ＥＢ／ＯＬ］．［２０１２－０３—２５］．ｈｔｔｐ：／／ｗｗｗ．ｋａｉｘｉｎ００１．ｃｏｍ／． 国科学技术大学学报，２０１１，４１（７）：５６５—５７４． ［５］ ＫＵＭＡＲ Ｒ，ＮＯＶＡＫ Ｊ，ＴＯＭＫＩＮＳ Ａ．Ｓｔｒｕｃｔｕｒｅ ａｎｄ ｅｖｏｌｕｔｉｏｎ ｏｆ ＭＩＳＬ０ＶＥ Ａ．Ｋ０ＰＰＵＬＡ Ｈ Ｓ．ＧＵＭＭＡＤＩ Ｋ Ｐ． ａ／．ＧＩＤｗｔｈ ｏｆ ｔｈｅ ｏｎｌｉｎｅ ｓｏｃｉｌａ ｎｅｔｗｏｒｋｓ【Ｃ】／／Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ １２ｔｈ ＡＣＭ ＳＩＧＫＤＤ ｌｆｉｃｋｒ ｓｏｃｉｌａ ｎｅｔｗｏｒｋ『Ｃ１／／Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ １ｓｔ ＡＣＭ ＳＩＧＣＯＭＭ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｋｎｏｗｌｅｄｇｅ Ｄｉｓｃｏｖｅｒｙ ａｎｄ Ｄａｔａ Ｍｉｎｉｎｇ． Ｗｏｒｋｓｈｏｐ ｏｎ Ｓｏｃｉａｌ Ｎｅｔｗｏｒｋｓ．Ｎｅｗ Ｙｏｒｋ：ＡＣＭ Ｐｒｅｓｓ，２００￣：２５—３０． Ｎｅｗ Ｙｏｒｋ：ＡＣＭ Ｐｒｅｓｓ，２００６：６１１—６１７． ［１２］ 张彦超，刘云，张海峰，等．基于在线社交网络的信息传播模型 【６］ ＭＩＳＬＯＶＥ Ａ，ＭＡＲＣＯＮ Ｍ，ＧＵＭＭＡＤ Ｋ Ｐ，ｅｔ ａ１．Ｍｅａｓｕｒｅｍｅｎｔ 【Ｊ】．物理学报，２０１ｌ，６０（５）：６０—６６． ａｎｄ ａｎａｌｙｓｉｓ ｏｆ ｏｎｌｉｎｅ ｓｏｃｉａｌ ｎｅｔｗｏｒｋｓ［Ｃ］／／ＩＭＣ＇０７：Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ［１３】 ＦＲＡＵＥＮＴＨＡＬ Ｊ Ｃ．Ｍａｔｈｅｍａｔｉｃａｌ ｍｏｄｅｌｉｎｇ ｉｎ ｅｐｉｄｅｍｉｏｌｏｇｙ［Ｍ］． ｔｈｅ ７ｔｈ ＡＣＭ ＳＩＧＣＯＭＭ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｉｎｔｅｒｎｅｔ Ｍｅａｓｕｙｅｎｅｎｔ．Ｎｅｗ Ｂｅｒｌｉｎ：Ｓｐｒｉｎｇｅｒ，１９８０．
