一种机会网络重叠社区检测方法

发布时间：2018-05-02 06:49

本文选题：机会网络 + 重叠社区　；参考：《新疆大学》2014年硕士论文

【摘要】：机会网络是一种不需要源节点和目标节点之间存在完整链路，利用节点移动带来的相遇机会进行通信的新的网络模式，对于实现未来普适计算具有重大影响。随着对实际网络的深入研究，研究者们发现很多实际网络中不仅具有社区结构，而且社区间存在彼此重叠和相互关联的特性。作为研究网络结构的基础，揭示网络中的社区结构对研究网络的功能和分析网络的组成结构具有十分重要的意义，重叠社区检测成为机会网络结构研究的关键问题。针对机会网络中社区重叠问题，提出一种基于边权重局部扩展的重叠社区检测方法。算法根据机会网络节点接触产生的相遇时间和相遇间隔时间信息，计算节点间的关系强度将其作为网络中边的权重，并使用滑动窗口方法建立机会网络拓扑结构。然后在得到的网络拓扑图上，随机选择一个节点标记为初始社区，使用局部扩展方法进行扩展，为了使在加权网络中的扩展过程更精确，设计了一个基于局部适应度及内密度函数的优化目标函数用来控制社区扩张，扩展开始时先计算社区的邻居节点对其的归属度值，将最大归属度值的节点作为待扩展节点，再计算目标函数值增加与否，如果增加则把该节点并入初始社区，，继续向邻居节点扩展，否则确定该扩展区域为一个社区，然后继续选择下一个未分配社区的节点进行扩展，直到所有节点分配了社区。针对局部扩展方法中存在的初始节点选择随机、重复计算的不足，给出一种适合加权重网络中的利用节点聚集系数对初始节点进行选择的局部扩展优化策略。为验证算法性能，本文使用ONE模拟器进行实验仿真，并在该平台上实现基于社区的移动模型，并与NBDE算法对产生的仿真数据进行分析，比较社区划分的正确率，实验表明本文算法能够较准确的检测节点社区归属，并能够得到更加精确、稳定的重叠社区结构。
[Abstract]:Opportunistic network is a new network mode which does not need to have a complete link between the source node and the target node, and makes use of the encounter opportunity brought by the node movement to communicate, which has great influence on the realization of future pervasive computing. With the in-depth study of practical networks, researchers have found that many practical networks not only have community structure, but also overlap and correlate with each other among communities. As the basis of studying the network structure, it is very important to reveal the community structure in the network to study the function of the network and to analyze the structure of the network. The overlapping community detection has become the key problem in the research of the opportunity network structure. In order to solve the community overlap problem in opportunity networks, an overlap community detection method based on local expansion of edge weight is proposed. Based on the encounter time and encounter interval information generated by the contact of the nodes in the opportunistic network, the relational strength of the nodes is calculated as the weight of the edges in the network, and the topological structure of the opportunistic network is established by using the sliding window method. Then, on the network topology graph, a node is randomly selected as the initial community, and the local expansion method is used to expand the network, in order to make the expansion process in the weighted network more accurate. An optimization objective function based on local fitness and internal density function is designed to control community expansion. Then calculate whether the value of the objective function is increased or not, if added, merge the node into the initial community, continue to extend to the neighbor node, otherwise determine that the extended area is a community, and then continue to select the node of the next unallocated community for expansion. Until all nodes are assigned to the community. Aiming at the deficiency of random selection and repeated calculation of initial nodes in the local expansion method, a local expansion optimization strategy suitable for the selection of initial nodes using node aggregation coefficients in weighted networks is presented. In order to verify the performance of the algorithm, this paper uses ONE simulator to carry on the experiment simulation, and realizes the community based mobile model on this platform, and analyzes the generated simulation data with the NBDE algorithm, and compares the correct rate of community partition. Experiments show that the proposed algorithm can detect node community ownership accurately and obtain more accurate and stable overlapping community structure.
【学位授予单位】：新疆大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TP393.02

【参考文献】