Size reduction of complex networks preserving modularity Page: 3 of 14
This article is part of the collection entitled: Office of Scientific & Technical Information Technical Reports and was provided to Digital Library by the UNT Libraries Government Documents Department.
- Adjust Image
- Rotate Left
- Rotate Right
- Brightness, Contrast, etc. (Experimental)
- Download Sizes
- Preview all sizes/dimensions or...
- Download Thumbnail
- Download Small
- Download Medium
- Download Large
- High Resolution Files
- Accessibility
- View Extracted Text
Extracted Text
The following text was automatically extracted from the image on this page using optical character recognition software:
Size reduction of complex networks preserving modularity
and the total strength is
2w = " = j = WI2. (1.5)
The input and output strengths are equal (wi = wiout = wi"') if the network is
undirected, thus recovering the standard definition of strength. Furthermore, if the
network is unweighted and undirected, wi represents the degree of the i-th node, i.e. the
number of edges attached to it, and w is the total number of links of the network.
The challenge of optimizing the modularity has deserved many efforts from
the scientific community in the recent years. Provided the problem is NP-hard,
only optimization heuristics have been shown to be competent in finding sub-
optimal solutions of Q in feasible computational time. Nevertheless, when facing the
decomposition in communities of very large networks, optimality is usually sacrificed in
favor of computational time.
Our goal here is to demonstrate that it is possible to reduce the size of complex
networks while preserving the value of modularity, independently on the partition under
consideration. The systematic use of this reduction allows for a more exhaustive search
of the partitions' space that usually ends in improved values of modularity compared
to those obtained without using this size reduction. The paper is organized as follows:
In the next section we present the basics for the size reduction process. After that,
we provide analytic proofs for specific reductions. Finally we exploit the reduction
process based on the mentioned properties, and compare the modularity results with
those obtained without size reduction in several real networks, using the Extremal
Optimization heuristics [8].
2. Size reduction preserving modularity
2.1. Reduced graph
Let G be a weighted complex network of size N, with weights wi > 0, i, j E {1, ..., N}.
If the network is unweighted, the weights matrix becomes the usual connectivity matrix,
with values 1 for connected pairs of nodes, zero otherwise. We will assume that the
network may be directed, i.e. represented by a non symmetric weights' matrix.
Any grouping of the N nodes of the complex network G in N' parts may be
represented by a function R : {1,... , N} -> {1,... , N'} which assigns a group index
Ri = R(i) to every i-th node in G. The reduced network G' in which each of these
groups is replaced by a single node may be easily defined in the following way: the
weight wX between the nodes which represent groups r and s is the sum of all the
weights connecting vertices in these groups,
w = Z wi(Ri, r)(Rj, s) , r, s c {1, ... ,N'} (2.1)
1 j
where the sums run over all the N nodes of G. For unweighted networks the value of
Wr% is just the number of arcs from the first to the second group of nodes. It must be3
Upcoming Pages
Here’s what’s next.
Search Inside
This article can be searched. Note: Results may vary based on the legibility of text within the document.
Tools / Downloads
Get a copy of this page or view the extracted text.
Citing and Sharing
Basic information for referencing this web page. We also provide extended guidance on usage rights, references, copying or embedding.
Reference the current page of this Article.
Arenas, A.; Duch, J.; Fernandez, A. & Gomez, S. Size reduction of complex networks preserving modularity, article, December 24, 2008; Berkeley, California. (digital.library.unt.edu/ark:/67531/metadc893339/m1/3/: accessed April 20, 2018), University of North Texas Libraries, Digital Library, digital.library.unt.edu; crediting UNT Libraries Government Documents Department.