Information Technology Reference
In-Depth Information
represents a strong compression of the information, they may prove very useful and
effective. They are defined as follows.
Let k
v
be the connectivity of v, i.e. the number of links which connect node v (to
other nodes in the graph) in graph G; the average of k
v
over all the nodes is the
average degree of connectivity k of graph G.
A path between node a and b is defined as an ordered set of links which start from
node a and end in node b (or viceversa) such that any node is traversed only once; the
length of a given path is the number of links it contains. The distance between a pair
of nodes a and b, d(a,b), is the length of a shortest path between the two nodes. For
each vertex v let d
v
be the average of d(v,a) taken over all the other n-1 nodes. The
characteristic path length L of graph G is then the median of d
v
taken over all the
vertices [7].
The
neighbourhood
(v) of node v is the subgraph consisting of the nodes adjacent
to v (excluding v itself). Let
(v), i.e. the number of
links which connect nodes which are both adjacent to v. The clustering coefficient of
node v is the ratio between this number and the maximum number of possible edges
in
v
be the number of edges in
(v). i.e.:
ε
(
1
)
v
γ
=
v
k
v
2
The
clustering coefficient
C of graph G is then defined as the average of
v
, taken
over all the nodes of the graph.
A graph is
simple if multiple edges between the same pair of nodes are forbidden.
sparse, if k << n (the value corresponding to a "fully connected" graph)
connected, if any node can be reached from any other node by means of a
path consisting of a set of edges (there are no separate islands).
The topology of cellular automata is that of simple, sparse connected graphs that
are spatially regular, i.e. they are d-dimensional lattices. A one-dimensional CA ring
with degree of connectivity k is characterised by [7]:
(
)
3
k
−
2
(
2
)
n
n
+
k
−
2
n
.
C
=
L
=
≈
(
)
4
k
−
1
2
k
n
−
1
2
k
If the lattice were d-dimensional, L would scale as n
1/d
for large n, while C would
be independent from n.
The d-dimensional lattices constitute an important limiting case, and their natural
counterparts are the random graphs, which are defined by the fact that any pair of
vertices is connected by a link with a fixed probability p. In sparse random graphs
(p<<1) both
L
and
C
take small values for large n (for a thorough discussion, see [9]);
it turns out that the distribution of the number of connections per node is
approximately Poissonian and that L
log(n)/log(k), and C
p = k/n.
