1引言
近年，随着具有短距线通信能力（如BlueTooth、Wi-Fi、Zigbee等）的移动智能设（诸如智能手机、PDA、可设）的模普及，人们常生活中的信息可以几近完整地下，这不仅迚传统社会网络[1]及机会网络[2]信息感知、理和传播等领域的研究，也使得对人的真实社交情形迚行更加深О地研究以提出更加高的消息传播机制成为可能。随着移动互联网的兴起，作为社会网络和机会网络结合的产物，移动P2P社会网络[3]益受到研究学者的关注，成为线网络领域的一研究热点。移动P2P社会网络是一类节点间通过对等通信自组织组网形成的网络。该网络的节点是具有短距线通信能力的移动智能设。设虽法自主移动，Ξ赖其载（人）的社会性移动，设间可収生幵迚行信息交换，使这通信模式具有典型的社会性。移动P2P社会网络主要针对人的社会属性或人的移动性对网络动态性的影响、人的社会关系演化对网络形态演化的影响、如用人的社会性或移动性提升网络消息传播率等面内容[4]迚行研究。移动P2P社会网络的关研究不仅可应用于传统社会网络所涉及的瞬态社交网络、基于情景的移动社交、基于个性的广推送等面[5]，还对城市划、疫情扩散、社会关系掘与分析等领域有重要指导意[6]。如今这个社交活动从娱乐化向工具化过度的时代，移动P2P社会网络疑具有良好的研究前景和应用价值。而“追踪、収现对消息传播有关键作用的节点”这类问题，一是该领域的热点问题。移动P2P社会网络是杂网络的一，一面该类网络节点数目众多，另一面该类网络节点因具有杂的社会属性而使节点的移动模式杂多变，最终导致节点具有较的动态性。移动P2P社会网络中，节点间几乎不存完整的端到端径，节点不Ξ定的基础设施，采用“存储-携带-转収”的数据传输模式，用智能设的短距通信接以自组织的式与其它设収生而交换信息。由于节点各自的社会性上存差异，导致节点的移动性不同幵有不同的模式，最终使不同节点有不同的消息传播与消息获取能力。如这类网络中収现消息传播的关键节点，幵用其提升网络消息传播率成为研究学者们普关注的问题。已有的杂网络研究工作[7][8]中，学者借助社会网络分析法（SocialNetworkAnalysis，SNA）提出诸如Katz中心度、节点度中心性等测度用于衡节点信息传播过程中的重要性。这些研究多通过加历史数据将网络抽象为一张静态网络理，因此这些法未能完П现网络的重要——网络动态性与时变演化性。实际场景中，由于人的频繁社会活动使得节点间的关系随时间不动态变化，用加的法会造成重要信息的缺，法准确刻画网络的演化过程。如1所示，随着时间推移及网络演化，从拓扑角度看，节点A或节点B都能够将消息逐地、间接地传给节点F，是节点F却不能将消息传给节点A或节点B；而使用传统的加刻画网络后，从其拓扑结看，节点A或节点B与节点F间存可达径，表示节点A或节点B与节点F可迚行双向信息传。出现这错误是由于加中未能现网络演化的时向性。移动P2P社会网络是网络拓扑随时间不变化的时变动态网络，为准确刻画其拓扑演化过程，本文用时间演化模型（TimeEvolvingGraph,TEG）对其迚行建模分析。TEG模型将动态演化的网络抽象为随时间不变化的一系列拓扑快照序列，每个快照刻画一个时间间隔内的网络状态。需要说明的是，快照间时间间隔的选取法是目前仍定论的问题[9]，本文一面据经验值，一面据具的网络情景选取应的时间单迚行拓扑快照的划分。节点间传一个消息等于节点间产生或传一个影响，节点可对其他节点产生的总影响为节点的影响力[7]，而节点的中心性是表示节点影响力的常用测度[8]。本文使用节点的中心性测度作为其网络中传播消息时的关键程度的衡指标。传统基于通（walk）的节点中心性分析法，因静态网络不涉及时间因素，实质为只计算间维度上的所有长度通（可理解为是一张快照上的通）的加权和。与不同，本文同时考虑间维度和时间维度上的所有长度通（即动态通，包含只涉及某一快照的通和涉及多个快照的通）的加权和现某一节点对网络中其余节点的影响力。用通而不是“径（path）”或“最短径（theshortestpath）”迚行计算是因为移动P2P社会网络中的节点动态性较，节点间难以长时间维持稳定的通信链，而消息每个节点上的存储一般具有一定时长的生存期，节点会充分用每次的机会迚行最功率的信息传输保证将更多的消息传出去。这数据传输模式必然导致消息传过程中会经过重的节点或重的边，而通恰可以正确刻画这消息传径。另外，本文考虑对不同长度动态通迚行不同程度衰减的同时也考虑节点间的前后关系以及消息的实时性，用时间衰减因子对等步长产生时间对久进的动态通迚行更程度地衰减。这样做的原因于节点对网中其他节点产生的“影响”应随时间推移逐渐变得不再重要，即网络中的“消息”的影响力应随时间推移而衰减。本文针对移动P2P社会网络这类动态时变网络，借助SNA分析法幵结合静态物理学中计算粒子间性势能的“林函数”法，将静态网络中基于中心性指标的分析法扩展到移动P2P社会网络，用衰减因子分刻画消息的用随传播径长度衰减及随时间推移衰减这自然性，用节点的历史信息，提出一节点传播能力的化分析函数，刻画节点对时性消息的对传播能力。本文考虑消息的实时性，一面有助于化分析节点传播实时消息的能力，一面通过历史数据对一段时间内的节点消息传播能力迚行综合考虑，可识出“最近较活跃”的节点，将其作为实时性消息传播的关键节点从网络中众多节点中选出。基于真实Trace数据的实验表明，本文法可快速准确计算出各节点的消息传播关键程度，且用本法选出的关键节点作为消息传播的起始节点时，网络的消息覆盖速率明显提升。另外由于本文所述法考虑消息时个维度上所有可能的传播径，因此也可用于有预测网络的演化和不同节点未传播或获取消息时的对重要程度。某些的网络环境下，且衰减因子取值恰时，本文法的预测准确度最可达近90%。
2相关研究工作与现状
移动P2P社会网络由机会网络和社交网络结合而产生，是具有显著的拓扑动态性和演化性的一类杂网络。杂网络领域已有的研究工作[10][11]等用于研究人的移动性问题。基于这些工作，[12][13]提出基于节点不同连接机制的机会消息传法。是由于人移动性具有不可预知性使得网络高度动态性，移动P2P社会网络中研究拓扑演化律以及収现消息传播的关键节点成为一类具战性的问题。随着针对该领域的研究的增多，准确刻画网络形态的问题受到更多的关注。[14]提出随机的概念，然而由于随机的边独立性，使其不能很好地应用于动态网络分析，而[15]提出的时间演化模型则受到普的关注。该模型不同于静态论与随机，向网络中引О时间因素，将动态演化的网络沿时间向刻画为离散的拓扑快照序列。该模型可用于邻快照间研究拓扑演化性幵可单一快照内研究节点的间拓扑关系。针对网络内的关键节点収现问题，许多研究用SNA分析法提出基于中心性的研究法[7][8]，提出诸如度中心性、Katz中心性等测度。中心性度法最是基于静态网络提出的，所以幵不接适用于移动P2P社会网络这类动态网络。移动P2P社会网络中，因节点具有的个社会性差异，使得其消息传播能力上也存一定的差异，研究工作[16]针对该问题用真实数据验证这一点，是幵未提出有的分析模型或关键节点収现法。已有的研究[17]将基于通的中心性分析法从静态网络中扩展到动态网络中，用Katz中心度衡节点的影响力。是该法的数对快照拓扑形态的Ξ赖性较且不具有性，幵不易于用。研究工作[18]针对Email网络研究消息随时间传播应减的情ъ下提出评估节点传播能力的法。上述工作多基于通以及中心性的概念对节点的影响力或消息传播能力迚行度，其缺陷主要集中于个问题：1）上述有些工作基于静态网研究，不适用于动态网络分析；2）有些工作幵未考虑网络演化的时间因素，即消息的实时性或节点间产生影响的先后关系。本文为尽改正上述缺陷，网络动态性、节点间消息传烈Ξ赖于机会的移动P2P社会网络中，将传统的静态网络分析法扩展到动态网络的同时，充分考虑消息的实时性及节点间产生影响的先后顺序，提出移动P2P社会网络中传播实时消息的关键节点収现法，幵用真实环境采集的Trace数据对该法迚行验证。
3系统建模
3.1静态网络中节点的中心性
G(V,E)表示一个包含n个节点m边的权简单静态，V定为节点集合且Vn，E定为节点间连边的集合且Emm,nZ。G对应的nn维邻接矩阵表示为a(i,jV)ijΑ，节点i,j间存连边时1ija，否则0ija。由于G为权简单静态，0iia。本文用通而不是“径”或“最短径”迚行计算是因为移动P2P社会网络中的节点因其载的社会性而具有高度动态性，节点间几乎不存完整端到端径，幵且难以长时间维持通信链的稳定。节点采用“存储-携带-转収”的数据传输模式，而每个节点一般只一定时长的消息生存期内携带该消息，节点会充分用每次的机会迚行最功率的信息传输保证将更多的消息传递出去。这数据传输模式必然导致消息传过程中会经过重的节点或重的边。“径”或“最短径”不存重的边或点，而通却可以正确刻画这消息传径。现给出静态网络中通的定。
3.2动态演化网络中节点的中心性刻画
移动P2P社会网络是动态性的一类网络，节点的社会性移动使节点间的连边不产生和消。为最程度捕捉网络的动态演化性，本文用时间演化模型对该类时变网络迚行建模和分析，使用中心性指标作为判节点关键程度的Ξ据，幵将传统的基于通的中心性计算法扩展到时变网络中。此首先给出时间演化的定。
4实验验证
4.1实验数据
为验证本文提出的传播实时消息的关键节点収现法的有性，本节我们采用CRAWDAD[19]提Ν的于真实环境采集的Trace数据对我们提出的法迚行若干验证。本文选取基于常用线通信接Bluetooth与Zigbee于真实环境采集的数据迚行实验。Bluetooth接是较常用的通信接，Zigbee虽然不是智能终端的标准配置，由于它通信连接耗时更短（毫级）、通信耗能更等点使其具有良好的应用前景。这短距通信接的物理性使这接采集的数据可以较准确的刻画移动P2P社会网络的网络情形，且这通信接是移动P2P社会网络消息传输较为理想的选，具有较的应用前景。本节实验所用的数据集具为：1）2009年SigComm会议期间，100个持有HTCs620手机的用用Bluetooth接的数据；2）2008年安德鲁学校内27名携带传感器的人员79内通过Zigbee接的信息。组数据用不同的通信接，分展示会议场景及校场景这不同的数据采集环境的不同网络性。针对这具有差的数据集迚行实验，可验证本文法具有普适用性。表1列出实验数据的基本信息。
4.2不同节点的消息传播效率
网络中不同个的社会属性щ定其对消息具有不同的传播能力。本文提出传播实时消息的关键节点収现法，找到幵用这些关键节点提升网络的消息传播率。为验证这一目的，本实验首先用本文的法针对各个数据集分找到消息传播时关键程度最与最的个节点，后分将这个节点作为消息传播的源节点，网络中迚行洪泛（flooding）。由于移动P2P社会网络中节点间是间歇性连通的，洪泛式因具有冗余分収等性，使其对动态网络具有较好的自适应性，可以比较准确地刻画基于通的消息分収，本实验选取洪泛式迚行消息传播。另外，研究工作[20]表明：2-copy（对同一消息而言，节点对其至多转収2次）与副本洪泛式的网络覆盖速率几近同，所以本实验用2-copy洪泛式消息传播过程中的网络开销。为使实验结果更加，本实验计算出网络覆盖率的平情ъ，与定节点为消息源时的网络覆盖率迚行对比。从2给出的实验结果可看出：用本文法选出的关键程度最的节点作为消息源迚行消息传播的速率明显是最快速的。该实验结果清晰表明，用本文提出的法作为传播实时消息的关键节点的収现法，可以提升网络的消息覆盖速率。网络消息覆盖速率提升，表示实时性消息可快速地被传给网络中的各个节点。
4.3路径因子
对节点传播能力排名的影响本实验针对径因子对节点关键程度排名的影响迚行讨论。用于对具有不同长度的动态通迚行衰减，使得“短动态通对计算节点传播能力的贡献度较，长动态通对计算结果的贡献度较”。实际中，一面可据网络的动态程度，一面可据需要传播的消息的具性按照经验值设定的具取值。本实验中，我们针对各个数据集随机选取网络中的某一节点作为测节点，考察分取（0.1，0.3，0.5）时，该节点网络中的关键程度的排名变化情ъ。如前文所述，时间间隔的选取问题是仍未有定论的问题。迚行本节及后关实验时，我们首先据数据集的网络性，按照已有研究[9]对时间间隔的设置法，将Sigcom的时间间隔设为4.08时、Sassy的时间间隔设为1。另外本节将时间衰减因子取0，表示此实验暂不考虑时间因素只考察径因子对节点传播能力排名的影响。本实验随机选节点（Sigcom中选中节点15，Sassy中选中节点5），应用本文提出的法计算节点的消息传播能力排名。实验结果如3所示，横坐标表示各个快照的产生时间，坐标表示节点该时刻的关键程度（消息传播能力）排名，随着取值变，节点关键程度排名变化更加剧烈，幵最终趋于平稳。这是由于本法考虑节点可产生的所有长度的动态通，幵且的取值变时，不同长度动态通间的贡献度差异会缩，的取值变时，不同长度动态通间的贡献度差异会变，所以取值变时，节点关键程度的计算结果会受到较的影响，最终导致节点关键程度排名变化较剧烈，幵且时间累到一定程度时，节点的排名受历史的影响而趋于平稳。4.4时间因子对节点传播能力排名的影响本实验考察增加时间因素后，时间衰减因子对节点关键程度排名的影响。为保持一致性，本实验用前一实验针对各数据集随机选出的节点继续迚行测（Sigcom中选中节点15，Sassy中选中节点5）。从前实验的结果可看出，不考虑时间因素时，取值较，节点的排名变化较不明显。所以本实验中将各个数据集设为0.5，每个数据集中分取（0.1，0.5，1）测节点关键程度排名的变化趋势。
5结束语
本文针对移动P2P社交网络这类动态时变网络，提出一传播实时消息的关键节点収现法。该法借助SNA法将传统的杂网络中基于静态网络的中心性指标分析法扩展到时变动态网络中，将传统的通概念延伸为动态通概念。本文一面照静态物理学中的“林函数”公式为不同长度的动态通设置衰减因子，一面考虑拓扑演化的时向性及消息的实时性，设置时间衰减因子对不同“年龄”的消息迚行不同程度的衰减，最终以迭代式计算出动态通的加权和，得到传播实时消息的关键节点评价函数。5组基于真实数据的实验验证本法的正确性的同时，还表明本法可一定程度的上对节点的消息传播与获取能力迚行预测。本文提出的传播实时消息的关键节点収现法，虽然法理论和实验上验证为是正确有的，仍有以下缺陷需要继续完善：1）时间间隔的选取问题是目前仍研究阶段的问题，时间间隔不于用本文所用的“等时间间隔”划分形式，幵且时间间隔选取的也会带很多问题，例如时间间隔划分过会使得快照内的信息不完整；时间间隔划分过会使得快照中存过多的冗余信息。本文按照数据的采集背景以及经验值设置时间间隔是一奈的折中策略，迚一步针对时间间隔选取的研究是有必要且是十分重要的。2）衰减因子的取值问题。本文按照研究目标以及网络状ъ设置衰减因子，幵通过实验测衰减因子对结果的影响，我们认为衰减因子应存取值的上下界或是针对不同网络状态有最优选，研究网络状ъ和衰减因子的取值关系是很有必要的。3）本文假设消息的生存期是，即不考虑节点会主动弃所携带消息的行为。不同网络状ъ下，消息的生存期的设置式不同，该项工作虽不与本文工作接关，若考虑消息的生存期问题将有助于提升本文法的普适性。4）选取合理的时间间隔以及运用合适的矩阵计算法都会接影响本文所提法的杂度，本文着重提出一较颖的动态网络中収现关键传播节点的法，分析医学期刊在线幵迚一步找到法提升本文所提法的算法率是我们下一步的工作。针对上述工作，我们会下一阶段迚行重点研究。
作者：白宇清 李海健 蔡青松 单位：北京工商大学 廊坊师范学院数学与息科学学院
