Database Reference
In-Depth Information
G
:
0
1
2
3
G
:
0
1
2
2
G
:
1
2
3
G
:
1
2
G
:
0
1
2
3
G
:
0
1
2
3
G
:
0
1
2
3
G
:
0
1
2
G
:
1
2
3
Fig. 2.
All possible medians of the sequence (
G
1
,G
2
) from Fig. 1.
Comparing the median graph construction procedure for
d
1
with the one
for
d
2
, we notice that the former is a special case of the latter, constraining
edge weights to assume only binary values. Edge weight zero (or one) indi-
cates the absence (or presence) of an edge. Including an edge (
u, v
)inthe
median graph
¯
G
because it occurs in more than
n/
2 of the given graphs
is equivalent to labeling that edge in
ˆ
G
with the median of the weights
assigned to it in the given graphs.
The median of a set of numbers according to Eq. (5.2) is unique. Hence
when constructing a median graph under graph distance measure
d
2
,there
will be no ambiguity in edge weights. But the non-uniqueness of the exis-
tence of vertices observed for graph distance measure
d
1
still exists under
d
2
. The convergence property holds also for
d
2
, because for any sequence
of edge weights (
x
1
,...,x
k
) one has:
median(
x
1
,...,x
k
)=median(
x
1
,...,x
k
,
median(
x
1
,...,x
k
))
.
