Database Reference
In-Depth Information
Fig. 3.14 Two similar
networks, the first one having
one dominant node with
higher closeness
Fig. 3.15 Two networks with
similar number of nudes, but
different clustering
coefficients
3.1.6.6 Clustering Coefficient
The local clustering coefficient describes the neighborhood of some node in terms
of its interconnections. It can be computed using
degree
ð
v
Þ
C C ð
v
Þ¼
Þ ;
j
N
jðj
N
j
1
where N is the set of nodes connected to the node v . Figure 3.15 shows two network
with the same number of nodes. The first one is less interconnected; therefore, the
nodes have a smaller clustering coefficient value. The second one contains a lot of
cliques; therefore, the nodes have higher clustering coefficient values.
This measure can be simply extended to the whole networks (so-called global
clustering coefficient) using the concept of connected triplets and triangles.
3.1.7 Complexity Aspects
As can be seen from both the mentioned paper and experiments presented below,
with the increasing range of input data, the Galois lattice soon becomes very
complicated and the information value decreases. The computational complexity
increases rapidly.
A comparison of the computational complexity of algorithms for generating a
concept lattice can be found in [ 25 ]. As stated in the paper, the total complexity of
lattice generation depends on the size of input data, as well as on the size of the
output lattice. This complexity can be exponential. An important aspect of these
algorithms is their time delay complexity (the time complexity between generating
two concepts). Recent paper [ 15 ] describes a linear time delay algorithm. In many
Search WWH ::




Custom Search