Abstract: Conventional methods of finding key nodes in a network are mainly based on the theory of static graph, and cannot be applied to dynamic settings where connections between nodes appear and disappear dynamically. This paper focuses on a dynamic and evolving network, called mobile peer-to-peer social network (MPPSN), and proposes an efficient method on it to quantitatively identify the key nodes in the network. By extending the classical concept of centrality to the dynamic MPPSNs and using two elastic attenuation factors to characterize the walk-length fading effect and the freshness of a time-bound message, this paper precisely derives an iterative matrix function to compute the relative importance of a node in MPPSN. Extensive experiments based on two real Trace datasets are conducted, and the results show that the analytical model is not only effective at identifying the most effective node in disseminating or receiving the latest useful messages but can even predict the node’s future behaviors as well as the network evolution at a very high accuracy.

Key words: mobile peer-to-peer social network, time-bound message dissemination, centrality analysis method, dynamic walk

摘要： 传统的消息传播关键节点发现方法大多针对静态网络进行研究。针对移动P2P社会网络这类复杂的动态时变网络，提出了一种其时效性随时间和传播路径衰减的一般类型消息传播过程中关键节点的发现方法。将静态网络中基于通路（walk）的节点中心性分析方法扩展到移动P2P社会网络中，将消息传播路径分解到时间-空间两个维度上，并利用两个衰减因子分别刻画消息的效用随传播路径长度衰减及随时间推移衰减这两种自然特性，利用节点的历史相遇信息，得到了节点传播能力的量化分析函数，以此刻画节点对时效性消息的相对传播能力。基于真实Trace数据的实验结果验证了该方法的可行性。由于所述方法考虑了消息时空两个维度上所有可能的传播路径，也可用于有效预测网络的演化和不同节点在未来传播或获取消息时的相对重要程度。

关键词: 移动P2P社会网络, 实时消息传播, 中心性分析方法, 动态通路