Image Processing Reference
In-Depth Information
according its total weight m .
The simplest method to combine multi-layer graphs is to make the average of all layers:
L
l A l ;
L
l
L
l m l ;
1
L
1
L
1
L
1
2 m Tr
A
d
G T ¯ MG
=
=
d l ;
m
=
ax Q
=
max
G
(
)
(35)
Then the community membership matrix G may be found by one of community detection
methods described before. By taking into account degree distributions of nodes at each graph
layer, the total modularity across all layers may maximized as (Tang et all, 2009)
Tr G T
G
L
l Q l = max
L
l
d l d l
L
l
1
L
1
2 L
1
L
G T M l
=
(
A l
2 m l )
=
(
)
max Q
max
G
Tr
2 m l G
,
(36)
G
Similar approach, but applied to graph Laplacian spectra and extended with a regularization,
is used in (Dong et al, 2011).
Typically networks describing social relations are often undersampled, noisy and contain
different amount of information at each layer. As the result, a noisy or an observable part(s) in
one of the layers after averaging in (35) and (36) may deteriorate the total accuracy. A possible
solution for this problem is to apply weighted superposition of layers. In particular, the more
informative the layer l is, the larger weight w l it should be given. For example, we may weight
the layer l according to its modularity Q l ,hence
L
l w l A l =
L
l Q l A l ;
1
L
1
L
A w
=
(37)
Another method to improve the robustness of nodes classification in multi-layer graphs
is to extract structural properties G l at each layer separately and then merge partitions
(Strehl & Ghosh, 2002). The more advanced approach of processing of multi-dimensional data
may be based on presenting multi-layer graphs as tensors and apply tensor decomposition
algorithms (Kolda & Bader, 2009) to extract stable communities and make de-noising by
lower-dimension tensor approximation.
These methods are rather involved and will be
considered elsewhere.
6. Simulation results for benchmark networks
To test algorithms described in the previous sections we use the karate club social network
(Zachary, 1977). As mentioned before, to get different hierarchical levels beyond and below
the resolution provided by max -modularity, we use the random walk approach. A number
of detected communities in the karate club at different resolution levels is presented at Fig.5.
As one can see, the max -modularity algorithm does not necessary result in the best partition
stability. The most stable partition in case of the karate club corresponds to 2 communities
(shown by squares and circles at Fig.1), which is in line with results reported by (Zachary,
1977).
Comparison of coupling scenarios B.2 and B.3 is presented at Fig.6 and Fig.7.
Pair-wise
correlations between oscillators at t
1 for coupling scenarios B.2 and B.3 are depicted at
Fig.6. Scenario B.3 reveals clearly communities structure, while in case of B.2 the negative
coupling overwhelms the attractive coupling and forces the system into a chaotic behavior.
=
Search WWH ::




Custom Search