livro Network Science - Albert-László Barabási

Disponível online em http://networksciencebook.com/

Capítulo 2

Exemplos de datasets de redes reais

 

The basic characteristics of ten networks used throughout this book to illustrate the tools of network science. The table lists the nature of their nodes and links, indicating if links are directed or undirected, the number of nodes (N) and links (L), and the average degree for each network. For directed networks the average degree shown is the average in- or out-degrees ‹k› = ‹k_in›=‹k_out› (see Equation (2.5)).  

In a complete graph each node is connected to every other node. A complete graph is often called a clique, a term frequently used in community identification. 

 

Sparseness has important consequences on the way we explore and store real networks. For example, when we store a large network in our computer, it is better to store only the list of links (i.e. elements for which A_ij ≠ 0), rather than the full adjacency matrix, as an overwhelming fraction of the A_ij elements are zero. Hence the matrix representation will block a huge chunk of memory, filled mainly with zeros

 

A bipartite graph (or bigraph) is a network whose nodes can be divided into two disjoint sets U and V such that each link connects a U-node to a V-node. Medicine offers another prominent example of a bipartite network: The Human Disease Network connects diseases to the genes whose mutations are known to cause or effect the corresponding disease. 

The shortest path between nodes i and j is the path with the fewest number of links. In practice we use the breadth first search (BFS) algorithm.Cycle: a path with the same start and end node. Eulerian Path: a path that traverses each link exactly once. Hamiltonian Path: a path that visits each node exactly once. 

 

The diameter of a network, denoted by d_max, is the maximum shortest path in the network.

A network is connected if all pairs of nodes in the network are connected.  

Clustering coefficient captures the degree to which the neighbors of a given node link to each other.