Information Technology Reference
In-Depth Information
www.allworldautomotive.com
www.btztradeshows.com
By doing so, we attach
-1
(Radiators) to ontology
O
and we get a new graph as in
Figure 6. In [1,2] the graph-theoretic properties of such structures is discussed, show-
ing that they are scale-free networks as characterized in [3,4,5].
We are now in condition to identify ontology concepts with the communities origi-
nated by classification. We start with the definition of community . A
graph
G is an
ordered pair (
V
,
E
) where
V
is a finite set whose elements are called nodes and
E
is a
binary relation on
V
. An element of
E
is called edge. A
subgraph
W of G is a pair
(
V
',
E
') where V' is a subset of
V
' and
E
' is a subset of
E
.
Definition 1.
Let
G
be a graph. A weak community in
G
is a subgraph
W
of
G
such
that the number of edges internal to
W
is greater than the umber of edges external
to
W
.
ϕ
Definition 2.
Let
G
be a graph. A
strong community
in
G
is a subgraph
W
of
G
such
that, for any node in
W
, the number of edges internal to
W
is greater than the number
of edges external to
W
.
Of course, strong communities are also weak communities. Now we define the con-
cept of smallest community generated by a graph.
Definition 3.
Let
W
be a subgraph of
G
. The smallest strong (weak) community gen-
erated by
G
is a subgraph
C
(
W
) of G such that
i)
C
(
W
) is a strong (weak) community
ii)
C
(
W
)
W
iii) If
C
' is a community and
C
'
⊇
⊇
W
then
C
'
⊇
C
(
W
)
The construction of
C
(
W
) is straightforward and is given by the following algorithm
1.
Input a graph
W
=(
V
',
E
') of the graph
G
=(
V
,
E
)
2.
for any node
ν∈
V
'
3.
if
the number of internal arches of n is greater than the
number of its external arches
begin
E
υ
= {(
ν
,
a
) |
a
∈
V
}
V
ν
= {
a
∈
V
| (
ν
,
a
)
is external to
W
}
V
=
V
∪
V
ν
,
R
=
R
∪
R
ν
Go to 2
end if
When the algorithm stops, the graph W will become
C
(
W
).
C
(
W
) is also called the
community generated by W
.
