1888 M.-y. Zhou et al. / Physica A 391 (2012) 1887–1893
of real communication networks in modern society, the information that any one of the vertices has about the topology
of network is incomplete. Thus, many experts focus on the distributed navigation using local information of the topology
of the network. For instance, Zhou found that the mixing of the random walk and shortest path strategies can remarkably
enhance the efficiency of navigation [23]. Boguñá et al. generated Internet-like scale-free networks with high navigability by
embedding vertices into hyperbolic metric space and adding links between nearby vertices according to probability [24,25].
Zhuo et al. investigated that the navigation based on distance between vertices in the hidden metric space can efficiently
deliver a message in a small-world network through a process of information exchange and accumulation [26].
On the other hand, it has been revealed that the community structure exists in these communication networks
(e.g. Internet [27] and WWW [28–31]), in which a group of vertices from dozens to hundreds tend to make up a cluster
and organize in a hierarchical way [32]. The community structure makes the generation and evolution of networked system
much quicker and more stable than if the system is unstructured [33]. They also deeply affect the dynamics process occurring
in a networked system. For instance, the synchronization process could be hindered when the networked system opposes
the stronger community structure [34]. Understanding how messages pass through those networks with a community
structure and the impact of community structure on information transfer capacity are also important and significant for real
networked systems. The previous works [16,35] point out that community structure affects the navigability of messages,
however, they didn’t show that the traffic dynamics that simultaneously includes the navigation and transportation of
packets was influenced by the community. Here we simulate it on the scale-free network with a tunable community strength
and aim to quantitatively study the impact of the community on information transfer.
As both the packet routing strategy and network topology play essential parts in traffic flow, we systematically investigate
the traffic dynamics on scale-free network with tunable strength of community structure combined with local routing
strategy according to the degree of vertices. In the next section, we will describe the network construction and packet
routing strategy. In Section 3, simulations and a few analytical results are presented in both free and jammed state. In the
last section, we conclude our work.
2. The traffic model
As many real SF networks have an obvious community structure, we adopt a growth model to construct SF networks with
tunable strength of community structure. Inspired by two ingredients of the Barabási–Albert (BA) model, i.e. growth and
preferential attachment, the model is created as follows: We initialize completely connected networks with c communities
noted by U
1
,U
2
, . . ., U
c
, each of which has small number (m
0
) of vertices. Every time, a new vertex is added into a certain
community U
l
with m (m < m
0
) edges, where the n edges are linked to the vertices in community U
l
and the other m − n
edges are linked to these in other c − 1 communities. Specifically, we first choose n different vertices in community U
l
according to preferential attachment, which associates with the probability
∏
that a new vertex linking to vertex i (i ∈ U
l
)
relates to the degree k
i
of vertex i,
∏
= k
i
/
∑
j∈U
l
k
j
. Then for each one of the other m − n edges of the new vertex, we
randomly choose a community U
h
(U
h
= U
l
) and connect the new vertex to one vertex in community U
h
following the
aforementioned preferential attachment mechanism.
In our model, the degree distributions of vertices of both the whole network and each community obey the power
law with exponent approximate 3 when the network size is N = 10
3
[36]. They are also independent of the strength of
community that is quantified as [29,37]:
Q =
c
−
s=1
l
s
L
−
d
s
2L
2
, (1)
where c is the number of communities, L is the number of edges in the network, l
s
is the number of edges in community U
s
,
and d
s
is the sum of vertex degrees in community U
s
. For large N, in Eq. (1), L = mN, l
s
=
nN
c
, and d
s
=
2mN
c
[36]. Instead of
Eq. (1), we obtain
Q =
n
m
−
1
c
. (2)
Thus, by modulating m and n, the strength of community structure is tunable.
The traffic model is first proposed in Ref. [13], and to keep our description self-contained as possible, we briefly review the
model: there are R packets are generated in the system at every time step, and each one chooses its source and destination
randomly. The vertices can deal with at most C packets towards their destinations. A packet routing strategy that relates to
the local topology information is used to navigate packets. Concretely, if the packet’s destination is within the neighbor area
of searching vertex, it will be delivered directly to its target. Otherwise, the searching vertex will navigate the packet to one
of its neighbors with the preferential probability [13]:
Π
i
=
k
α
i
∑
j
k
α
j
, (3)