Database Reference
In-Depth Information
an edge, in
2, respectively. Obviously, any
graph resulting from this relaxed procedure is also a median of sequence
G
if
C
(
u
)=
n/
2, or
C
(
u, v
)=
n/
S
.
Consequently, for the graph distance measure
d
1
used in this section, several
medians for a given sequence of graphs may exist. They result from either
inclusion or non-inclusion of a vertex
u
(or an edge (
u, v
)) with
C
(
u
)=
n/
2
(or
.
An example of the situation where the median graph of a sequence is not
unique is shown in Figure 1. Here we have the choice for both vertex 0 and
3 and their incident edges of either including or not in the median graph.
This leads to a total of nine possible median graphs depicted in Figure 2.
Another property worth mentioning is the convergence property of the
median under distance
C
(
u, v
)=
n/
2) in
G
d
1
. That is, for any given sequence
S
G
1
,...,G
n
)
=(
of graphs,
median(
G
1
,..., G
n
)=median(
G
1
,..., G
n
,
median(
G
1
,..., G
n
))
.
Clearly, each vertex
u
and each edge (
u, v
) occurring in sequence
S
is
included in the median if and only if it occurs in
k>n/
2 graphs. Hence,
adding its median number of occurrences to set
S
will result in a median
. For example,
¯
that is identical to the median of
S
G
1
shown in Figure 2 is
¯
amedianof(
G
1
,G
2
) in Figure 1, but
G
1
is also a median of the sequence
(
¯
G
1
,G
1
,G
2
).
In the remainder of this section we derive a procedure for median
graph computation using the generalized graph distance measure
d
2
defined
in Eq. (4.2). We start again from
S
=(
G
1
,...,G
n
),
G
=(
V, E
)with
=
i
=1
V
i
=
i
=1
E
i
,andlet
V
and
E
C
(
u
)and
C
(
u, v
)bethesameas
introduced before.
Let graph
ˆ
=(
ˆ
ˆ
G
V,
E,
w
E
) be defined as follows:
ˆ
ˆ
V
=
{u|u ∈ V ∧ C
(
u
)
>n/
2
},
ˆ
ˆ
E
=
{
(
u, v
)
|u, v ∈
V },
{w
G
i
E
i
w
E
(
ˆ
u, v
)=median
(
u, v
)
|i
=1
,...,n}.
Then it can be proven that graph
ˆ
G
S
d
2
[33].
is a median of sequence
under
G
1
:
1
2
3
G
2
:
0
1
2
Fig. 1.
Two graphs (
G
1
,G
2
).
