动态社交网络中人群移动性分析

摘要

动态社交网络(DSN)已经成为普遍的新型通信模式，它采用随时间演进的社会特征和移动节点（即用户及其设备）的行为来设计有效且高效的网络协议。在DSN中，受到节点个体和社会行为以及环境参数的影响，节点具有非随机的移动性和一定的接触模式。因此，可以用社会网络分析技术（如中心性和社区）来探索这些运动模式，并提取它们之间有意义的模式和关系。
　　在网络中更精确地识别节点中心性非常有用，它可以让人设计更好的路由策略或以更适当的方式选择关键节点。中心性识别同样适用于具有犯罪和恐怖主义的网络。现在已经有了很多量化DSN中节点中心性的度量和算法，但是这些方法大都只研究节点和链路不会动态改变的静态网络。然而，动态变化的DSN带来了很多挑战，例如，由于节点自身的移动性，会引起节点之间的链路删除或链路增加。此外，关键玩家问题(KPP)的识别是社交网络研究的研究之一，KPP旨在识别网络中最有积极或消极影响的一组节点。人们可以利用积极影响了解一个节点在网络信息传递中的作用，利用消极影响检测节点造成网络损坏或断裂的关键程度。
　　我们在DSN中提出三个主要的研究问题，并提出我们的解决方案。
　　首先，我们完成了DSN中重叠社区的检测，根据各种相关因素提出一系列算法。首先，提出一个节点赋权机制，其作用是使具有亲密朋友关系节点间的权值和没有亲密朋友关系朋友间的权值具有细微的差别。然后，我们查看分组的群体，并以个体的方式查找他们的根源。这些连接社区反映了在现实生活里朋友之间是真的亲近，或者他们之间的连接是由集群结引起的。这些信息还会告诉我们，根据亲密度的不同，每个人会在多大程度上受到一个连接或朋友的影响。我们将依赖于源信息的开放性特征作为标签存储在指定的存储空间中。实验表明，F-Score，Nicosia，NMI这三个因素已经提出了一种特定的算法，这使得检测过程更加有用高效。
　　其次，我们设计出一种新方法来预测DSN网络中移动用户未来的中心性。中心性的概念在分析社会行为和采取理想行动，如机会网络中的数据路由和传输方面起着重要的作用。换句话说，预测移动用户的未来中心性有助于我们在能量有限的DSN中设计高效的路由协议。我们在计算用户当前和过去的中心度量之间的相关性的基础上制定我们的方法，使用向量来表示网络中心的状态。为了检查网络节点的行为，我们在实验中使用相关性和距离向量作为度量。此外，我们在三个真实世界的人力资源数据集(Intel，Cambridge和Infocom)上根据相关性和距离MSE的差异来分析我们方法的性能。实验结果表明，与标准的方法相比，在数据传播成功率和平均数据传输延迟方面，我们的方法具有更好的性能。
　　最后，我们提出DSN中的关键节点识别问题，并给出快速定位网络中最有影响力节点的方法，帮助我们更好地理解和控制网络节点的行为。由于大多数现有的现实社会网络具有随社会和时间变化的特征，因此在关键节点识别中研究个人的社会属性是非常重要的。所以，在本论文中，我们调查了一些重要的社会特征之间的相互关系，例如DSN节点的灵活性和社会性。我们的方案使用特定应用程序进行信息的网络传播。为此，我们设计了一个动态网络模型来为定义个人的社会属性，并探讨他们之间的意见传输。在实验中，我们评估了方法对信息传播的多组个体的有效性。通过从不同域选择不同的节点集合来分析社会属性和节点重要性之间的关系。进一步的实验，我们将提出的方法与现有方法在执行时间、传输率和开销比率进行了比较。

目录

声明

Abstract

摘要

CONTENTS

List of Figures

List of Tables

1 Introduction

1．1 Dynamic Social Networks (DSNs)

1．2 Dynamic Social Network Applications

1．3 Dynamic Social Network Analysis Techniques

1．3．1 Social Graph

1．3．2 Social-based Human Mobility

1．3．3 Centrality

1．3．4 Social similarity

1．3．5 Friendship

1．3．6 Social Community Structure

1．3．7 Social Tie

1．4 Problem Statement

1．5 Contributions and Novelty

1．6 Outline

1．7 Summary

2 Human Mobility Analysis Framework in Dynamic Social Networks

2．1 Introduction

2．2 Related Work

2．3 Human Mobility Characteristics

2．3．1 Spatial Characteristics

2．3．2 Temporal Characteristics

2．3．3 Contact Characteristics

2．4 Human Mobility Models

2．4．1 Real Mobility Traces

2．5 Simulation-based Mobility Models

2．5．1 Map-based Models

2．5．2 Location-based Models

2．5．3 Community-based Models

2．5．4 Sociological Models

2．6 Human Mobility Prediction

2．6．1 Location Prediction

2．6．2 Time Prediction

2．6．3 Contact Prediction

2．7 Summary

3 Detecting overlapping Communities in Dynamic Social Networks

3．1 Introduction

3．2 Related work

3．3 Proposed Algorithm

3．3．1 Calculating the Weight of Nodes

3．3．2 Primary Processing of Tags

3．3．3 Choosing Primary Points

3．3．4 The Stage of Interaction Simulation

3．3．5 Post Processing

3．4 Compared Algorithms

3．4．1 Algorithm CONGA

3．4．2 Algorithm CONGO

3．4．3 DOCA Algorithm

3．5 Computational Complexity Analysis

3．5．1 Complexity of CONGA

3．5．2 Complexity of CONGO

3．5．3 Complexity of DOCA

3．6 Performance Evaluations

3．6．1 Characteristics of Synthetic Networks

3．6．2 Experimental Procedure Description

3．6．3 Overlapping Communities in Synthetic Networks

3．6．4 Overlapping Communities in Real-World Social Networks

3．7 Results and Discussion

3．8 Summary

4 A Correlation-based Centrality Prediction Algorithm for Dynamic Social Networks

4．1 Introduction

4．2 Related Work

4．3 Centrality in Dynamic Network

4．3．1 Network Graph

4．3．2 Dynamic Network

4．3．3 Centrality Measure

4．4 Katz Centrality

4．5 Centrality Prediction

4．5．1 Computational Complexity Analysis

4．6 Compared Methods

4．6．1 DACCER

4．6．2 Semi-Locally Centrality Article

4．7 Performance Evaluation

4．8 Summary

5 A Social Feature-based Method to Identify Key Players in Dynamic Social Networks

5．1 Introduction

5．2 Related Work

5．3 Models and Definitions

5．3．1 Dynamic Social Network Model

5．4 Problem Statement

5．5 Social Feature-based Key Player Identification

5．5．1 Readiness

5．5．2 Sociability

5．5．3 Specialty

5．5．4 Flexibility

5．5．5 Opinion Update Mechanism

5．6 Simulations and Evaluation Results

5．6．1 Compared Methods

5．6．2 Comparision Results

5．7 Summary

6 Conclusion and Future work

References

Published Academic Papers during PhD Period

Acknowledgment

About the Author