# 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.

#### 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 September 19, 2018), University of North Texas Libraries, Digital Library, digital.library.unt.edu; crediting UNT Libraries Government Documents Department.