Database Reference
In-Depth Information
has a similar property as the median of a sequence of graphs: it minimises
the sum of distances to all elements of the given sequence i.e., it minimises
the expression
i
=1
|
.
Next we describe a procedure for the computation of the median
¯
x − x
i
|
G
of a sequence of graphs (
G
1
,...,G
n
) using the topological graph distance
=
i
=1
V
i
and
measure
d
1
defined in Eq. (4.1). Let
G
=(
V, E
)with
V
E
=
i
=1
E
i
.Furthermore,let
C
(
u
) denote the total number of occurrences of
vertex
u
in
V
1
,...,V
n
. Formally,
C
(
u
) is defined by the following procedure:
C
(
u
)=0;
for
i
=1to
n
do
if
u ∈ V
i
then
C
(
u
)=
C
(
u
)+1
An analogous procedure can be defined for the edges (
u, v
)
∈ E
:
C
(
u, v
)=0;
for
i
=1to
n
do
if (
u, v
)
∈ E
i
then
C
(
u, v
)=
C
(
u, v
)+1
¯
=(
¯
¯
Next we define graph
G
V,
E
)where:
¯
V
=
{u|u ∈ V ∧ C
(
u
)
>n/
2
},
¯
E
=
{
(
u, v
)
|
(
u, v
)
∈ E ∧ C
(
u, v
)
>n/
2
}.
Then it can be proven that
¯
G
1
,...,G
n
) [33].
Consequently, a practical procedure for computing the median of sequence
S
G
is a median of sequence (
of graphs is as follows. We consider the union of all vertices and all
edges in
S
. For each vertex
u
acounter,
C
(
u
), and for each edge (
u, v
)a
counter,
C
(
u, v
), is defined. For each instance of vertex
u
(and edge (
u, v
))
in sequence
S
,
C
(
u
) (and
C
(
u, v
)) is incremented by one. Finally, vertex
u
)) is included in
¯
(edge (
2). Obviously,
this procedure is linear in the number of vertices and edges, and in the
number of graphs in
u, v
G
if
C
(
u
)
>n/
2(
C
(
u, v
)
>n/
. In contrast to the general method discussed in [34],
which is computationally very costly, it can be expected that the procedure
introduced in this paper can handle long sequences of large graphs.
In [34] it was shown that the median of a set of graphs is not necessarily
unique. It is easy to see that the median graph computed by the procedure
introduced in this section is always unique. However, note that the condition
C
S
(
u
)
>n/
2and
C
(
u, v
)
>n/
2 can be relaxed by inclusion of a vertex, or
