Berita terupdate dan terpercaya


The analysis of the morphological characteristics of networks is based on the formalism of graph theory (Newman, 2003). A graph G = {V, E} is a mathematical entity formed by a set of nodes or vertices (V) and a set of edges or links (E), composing a network (Wilson, 1979). Let n be the number of nodes in V. Pairs of elements {i,j} of V forms the subset E, with 1 < i, j < n, which indicates the ends (nodes) connected by these edges. When the edges of a given graph have a specific direction, it is said that this graph is directed or oriented. Otherwise, the graph is undirected; that is, there is no orientation in the connection. It is also important to mention that in the representation of real systems, graphs can have functions that relate the sets of nodes and edges to a set of values, a situation in which the graph is denoted as valued or weighted.

2.1. Network Indicators

Newman (2003) presents several real systems that can be represented with this formalism, such as social networks (eg, interactions between individuals, physical or virtual), information networks (eg, citations of scientific works and referencing web pages), technological networks (eg, physical computer networks, energy and transportation systems) and biological networks (eg, interactions in a food chain, metabolic pathways and epidemiological evolution of pathologies). From this representation, it is possible to analyze the phenomenon studied employing indicators that characterize its topology. These attributes can be calculated both for specific elements that compose the network (nodes and edges), or the network as a whole.

In this sense, a fundamental measure in graphs is the node degree (k) that indicates the number of connections that a given node has. With this value, it is possible to define the degree centrality (CD), which consists of the ratio between the degree of a node i and the number of nodes (n) in a given graph (Equation 1).


Other types of centrality essential to characterize the network are the closeness centrality (CC) and the betweenness centrality (CB), as defined by Freeman (1978). Closeness centrality measures how close a node is to other nodes in the network. For a given node i, it is defined as the reciprocal of the shortest paths summation considering this node and all the others in G, as expressed in Equation 2.

Eq 2

Where d_ {ij} is the shortest path length between nodes i and j.

The betweenness centrality is calculated by the proportion of minimum paths that pass through a given node (Equation 3). Its value indicates the importance that a given node has when connecting the others as a means of moving between them:

Eq 3

Where jk is the number of minimum paths between nodes j and k, and jk (i) is the number of minimum paths between nodes j and k that pass through node i.

More recently, other indicators have been used to broaden the understanding of the characteristics of networks, such as PageRank (PR), developed by the creators of Google (Brin and Page, 1998). PageRank consists of a ranking algorithm for web pages, which helps to decide the relevance of these pages based on the quantity and importance of other pages that refer to it through hyperlinks. Thus, for a given web page (graph node), the PR can be calculated iteratively until convergence using the following expression (Equation 4):

Eq. 4

In Eq. 4, d is a damping factor (ranging from 0 to 1), n ​​is the number of nodes in the network, ON (i) is the set of nodes that point to node i and n_j is the number of nodes to which a given node is already connected. In the web context, the damping factor indicates the level of randomness of a user's navigation. The closer to value 1, the lesser the randomness, and the higher the probability that the page has been visited from other pages that have hyperlinks pointing to it. In this way, the more connections a given node has with other nodes that are also well connected, the higher its PR.


Post a Comment

Blog Archive

Definition List

Unordered List