机会网络中非稳态社会关系演化与社团划分

摘要

在具有社会性的机会网络中，节点间存在社会关系。社会关系紧密的节点形成社团。社会关系和社团关系是社会性机会网络中消息路由决策的核心依据，研究非稳态社会关系演化和社团划分具有很重要的科学意义。
　　目前，在机会网络社会性研究和以社会性为基础的路由策略研究中，大都假设社会关系是稳定的、静态的，以此为基础得到的社团是稳定不变的。但是，在机会网络的实际应用场景中，社会关系和社团关系通常是动态变化的，包括:节点只转发特定类型的消息，由不同类型消息反复交错构成的消息序列在网络中传播时，可用的社会关系和社团关系反复变化震荡，呈现为不稳定状态;节点具有移动性，节点相遇具有随机性，这造成了社会关系和社团关系随时间动态变化;节点间社会关系的紧密程度具有不确定性，以其为基础得到的社团也是不确定的、以概率形式存在的。
　　针对机会网络社会关系和社团关系动态变化的特性，论文分析和解决了在震荡不稳定的、动态演化的机会网络社会关系下划分社团的问题，主要包括三个相互联系的方面，即首先解决社会关系拓扑结构由于消息敏感而产生的震荡问题，将震荡非稳态社会关系转换为稳态的社会关系;其次，解决随时间动态演化的社会关系不可预测的问题，建立了预测模型，对未来社会关系进行预测;最后，在预测得到的社会关系基础上，建立了不确定社会关系，并解决了不确定社会关系上无法获得贴近实际的社团的问题。
　　本研究的主要贡献和创新性成果如下:
　　1.提出一种非稳态社会关系拓扑下的机会网络分层模型。在机会网络中，节点只转发特定类型的消息，不同类型消息在网络中传播时，可用的节点集不同，因此，由不同类型消息反复交错构成的消息序列在网络中传播时，可用的社会关系拓扑结构反复变化，表现为社会关系由于消息敏感而产生震荡不稳定状态，社团划分结果无法重用，增加了划分社团的时间。为了解决该问题，本研究提出了机会网络分层模型，消除了社会关系拓扑由于消息敏感产生的震荡不稳定状态，提高社团划分的可重用性，降低了社团划分时间。首先，将机会网络的物理节点集映射为与消息类型匹配的虚拟节点集，并以此为基础建立虚拟机会网络层;然后，在虚拟机会网络层上建立社会关系，此时，消息敏感的社会关系拓扑由震荡不稳定状态转化为稳态;最后，对虚拟层上的社会关系进行社团划分。该模型使得社团划分次数仅仅取决于消息类型的数量，而不会随消息序列中消息数量或者消息类型的交错方式而改变，减少了社团划分的时间。在消息数量相同的条件下，当消息序列中相邻位置消息的类型差异度分别为40％和100％时，采用机会网络分层模型进行社团划分的时间，与在物理机会网络上直接进行社团划分的时间相比，分别减少约58％和89％。
　　2.提出一种机会网络社会关系拓扑动态演化预测模型。机会网络社会关系随时间动态变化，社团划分须等待社会关系建立后才能进行，这增加了社团划分的等待时间。为了解决这个问题，本研究提出了一种基于马尔可夫模型的机会网络社会关系预测模型，准确预测社会关系，为社团划分节约了建立社会关系所需的等待时间，减少了消息转发的准备时间。首先，将机会网络的运行时间分解为等长的时间片，并在时间片内以节点的相遇状态为依据构建节点间的社会关系;其次，在时间片构成的序列中，记录节点对在不同时间片的相遇状态，并构建与时间片序列对应的节点对相遇状态序列;再次，根据上述节点对形成的相遇状态序列样本数据，利用马尔可夫模型为节点对建立相遇状态转移概率矩阵;最后，根据本研究提出的社会关系拓扑动态演化预测模型，预测下一个时间片的节点相遇状态。论文提出的机会网络社会关系拓扑演化预测模型，预测的准确率达到了80％以上。
　　3.提出一种基于社交亲密度的K派系过滤算法。目前，机会网络社团划分都是以节点间存在确定的社会关系为基础的。然而，在实际场景下，社会关系是由节点的相遇频率和通信成功率共同决定的，具有以概率形式描述的不确定性。为了解决在机会网络不确定社会关系中划分社团的问题，本研究提出了一种基于社交亲密度的K派系过滤算法。首先，根据节点相遇记录和通信记录构建机会网络的不确定社会关系模型;其次，提出了社交亲密度的概念，并根据社交亲密度定义了不确定社会关系中社团的意义;最后，提出了改进的基于社交亲密度的K派系过滤算法，该算法能够对不确定的社会关系进行社团划分，得到结构和意义都符合实际的社团。实验结果表明，在机会网络的不确定社会关系上，论文提出的基于社交亲密度的K派系过滤算法与已有的K-CLIQUE算法相比，能够在更多的时间片中(80％)获得合理划分结果。

目录

声明

摘要

图目录

表目录

缩略词目录

第一章 引言

1．1 论文的研究意义

1．1．1 机会网络的研究意义

1．1．2 路由策略是机会网络研究的核心问题

1．1．3 社会关系和社团划分是机会网络路由策略的基础

1．1．4 机会网络非稳态社会结构演化与社团划分研究有重要意义

1．2 论文的贡献

1．3 论文的组织

第二章 相关研究概述

2．1 机会网络的发展和应用

2．2 机会网络路由策略的研究现状

2．3 机会网络中社会关系和社团划分的研究现状

2．4 论文研究的问题

2．5 本章小结

第三章 非稳态社会关系拓扑下的机会网络分层模型

3．1 提出问题

3．2 相关定义

3．2．1 虚拟机会网络层

3．2．2 虚拟路径

3．3 分层模型构建算法

3．3．1 特定场景下建立分层映射模型

3．3．2 非特定场景建立分层映射模型

3．4 虚拟层上的拓扑模型

3．5 实验结果及分析

3．5．1 时间复杂度分析

3．5．2 实验结果分析

3．6 本章小结

第四章 机会网络社会关系拓扑演化模型

4．1 提出问题

4．2 相关定义

4．3 基于马尔可夫模型的网络拓扑演化预测方法

4．3．1 时间片内建立相遇拓扑

4．3．2 相遇拓扑向社会关系拓扑映射

4．3．3 基于马尔可夫模型的社会关系拓扑预测

4．4 社会关系拓扑预测算法分析

4．4．1 拓扑预测正确率分析

4．4．2 拓扑预测模型效率分析

4．5 实验结果与分析

4．6 本章小结

第五章 基于社交亲密度的K派系过滤算法

5．1 提出问题

5．2 相关定义

5．3 K-CLIQUE社团划分算法及其存在问题

5．3．1 社团划分相关概念

5．3．2 概率社会关系

5．3．3 概率社会关系的构建

5．3．4 K-CLIQUE算法局限性

5．4 基于社交亲密度的K派系过滤算法

5．4．1 社交亲密度

5．4．2 基于社交亲密度的K派系过滤算法

5．5 实验结果及分析

5．6 本章小结

第六章 结束语

6．1 论文工作总结

6．2 下一步研究工作

参考文献

致谢

作者攻读博士学位期间科研和获奖情况