社区结构对复杂网络通航性的影响研究

181 浏览量更新于2024-08-29 收藏 604KB PDF 举报

"社区结构对导航的影响" 在复杂网络的研究中，网络的动态行为与它的结构特性紧密相关，这是学术界长期以来关注的焦点。本文深入探讨了社区结构如何影响复杂网络的导航性能。社区结构是网络中节点的一种组织形式，其中的节点具有较高的内部连接密度，而与其他社区之间的连接相对较弱。这种结构在现实世界中的许多网络中都能找到，如社会网络、互联网和生物网络。为了研究这一现象，作者采用了基于界标的多维缩放（Landmark-based Multi-Dimensional Scaling, LMDS）算法，将网络嵌入到K维欧几里得空间中。LMDS是一种常用的数据可视化方法，它能够保留网络中节点之间的距离信息，使得网络在低维度空间中有意义地呈现。在这里，网络被设计为无标度配置，这意味着网络的度分布遵循幂律，具有少数高连接度的节点和大量低连接度的节点。同时，通过调整边的分配，可以控制网络的模块性，即社区的明显程度。在这样的网络模型上，研究人员通过模拟消息传递过程来评估导航性能。他们选取源节点和目标节点对，应用贪婪路由策略，即消息总是向当前邻居中距离目标最近的节点移动，以此在欧几里得空间中传递消息。实验结果揭示了一个有趣的现象：网络的可导航性，即成功传递的消息比例，与网络的模块化程度有正相关关系。这表明，强模块化的网络更利于信息的有效传播。此外，研究还发现，最佳的嵌入维度K大约是界标数的一半。这可能是由于在适当的空间维度下，网络结构的复杂性和导航效率达到了平衡，过高或过低的维度都会降低导航效果。关键词：导航、复杂网络、潜在空间、社区、LMDS 这篇研究工作不仅提供了对复杂网络导航性能的新见解，也为理解和优化实际网络中的信息传播提供了理论基础。社区结构对于网络导航的影响可能会影响网络设计，特别是在需要高效信息传输的系统中，如互联网路由和社交网络信息流等。同时，这些发现也对网络科学领域的其他问题，如网络的演化、动态行为分析以及网络的优化策略等方面具有重要的启示作用。

Physica A 392 (2013) 1902–1908

Contents lists available at SciVerse ScienceDirect

Physica A

journal homepage: www.elsevier.com/locate/physa

Effects of community structure on navigation

Biao Wang

, Zhao Zhuo

, Shi-Min Cai

a,b,∗

, Zhong-Qian Fu

Department of Electronic Science and Technology, University of Science and Technology of China, Hefei Anhui, 230026, PR China

Web Sciences Center, School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu Sichuan, 611731, PR China

a r t i c l e i n f o

Article history:

Received 12 March 2012

Received in revised form 26 November

2012

Available online 9 January 2013

Keywords:

Navigation

Complex network

Latent space

Community

LMDS

a b s t r a c t

The dynamic behaviors of the complex network are crucially affected by its structural

properties, which is an essential issue that has attracted much interest. In this paper,

the effects of the community structure on the navigability of complex networks are

comprehensively investigated. The networks we explored, each of which is embedded

in a K-dimension Euclidean space based on a landmark based multi-dimensional scaling

(LMDS) algorithm, are of scale-free configuration with tunable modularity, obtained by

regulating the proportion of edges in and between communities. Pairs of source and

target are selected from the nodes in the networks, and the messages are passed along

from source to target in this space based on the greedy routing strategy. The extensive

experiments we carried out suggest that, the higher navigability, defined by proportion of

messages successfully delivered, is related to stronger modularity of the complex networks.

In addition, the optimal dimension K of the embedding Euclidean space is found to be

approximately identical to half of the landmark number.

1. Introduction

Navigation is one of the fundamental dynamical properties of networks. In the 1960s, a series of experiments conducted

by Travers and Milgram [1] unveiled that messages could be delivered to a destination through only a few people in the large-

scale social networks, in which nobody is aware of the whole information of the network structures. This phenomenon is

known as the small-world (SW) property. Recently, the SW phenomenon further confirmed that about twenty percent of

letters were successfully delivered with an average 4–5 hops in the experiments performed, both in email and online social

service networks, based on a greedy routing strategy [2–4]. Moreover, networks from the fields of nature and technology

also show similar properties revealed by several empirical works [5–7]. In light of the pervasiveness of the SW phenomenon

in various kinds of networks, it turns out to be important to interpret this phenomenon, and work has been carried out.

For instance, Watts and Strogatz [5] proposed a model of an SW network with characterization of low diameter and high

cluster coefficient by adding random connections on a regular network. Following that, Kleinberg defined an infinite family

of network models that naturally generalize the Watts–Strogatz model based on a decentralized algorithm, with which a

high probability can be achieved to find short paths [8]. On the other hand, the investigation of navigation (e.g. passing

messages) in complex networks has shown that the network topological properties, such as the SW property, the exponent

of power-law distribution, and the number of long range connections have effects on their navigability [8–11].

The aforementioned SW structure and power-law degree distribution have described the global properties of network

topology, however, the local environment of nodes in many real networks is also explored, such as the so-called community

structure [12–17]. In general, a community is defined as a subset of nodes in which connections are dense and among

∗

Corresponding author at: Department of Electronic Science and Technology, University of Science and Technology of China, Hefei Anhui, 230026,

PR China.

E-mail address: shimin.cai81@gmail.com (S.-M. Cai).

doi:10.1016/j.physa.2013.01.001

下载后可阅读完整内容，剩余6页未读，立即下载

weixin_38724247

粉丝: 8
资源: 915

社区结构对复杂网络通航性的影响研究

动漫导航_导航动漫_html_动漫导航_动漫网导航_动漫导航网_

琳琅导航系统（带后台）

Navmol:盲人和视障人士的分子结构导航仪-开源

社区结构强度可调的无标度网络中的流量动态

losrios-api:用于访问结构化洛斯里奥斯社区学院课程数据的 API

JTP导航

产品经理对抖音的竞品分析资料：功能结构图、信息结构图

仿网易侧滑导航二级导航

基于Java社区医院挂号系统的毕业设计，采用B/S结构和JSP技术、Eclipse、MySQL数据库进行编写

动漫导航源码

最新资源