Network Science for Fun and Profit

• Senior Data Scientist, iovation
• johnnylogic@gmail.com
• www.johnnylogic.org

• Provide a basic conceptual structure for networks.
• Review network basics to give context to methods and models.
• Demonstrate a range of network analysis methods.
• Present a few uses of network model.
• Provide further resources and code for future use.

Part 1: Network Science Motivation

Part 2: Network Science Basics

• Graph Types and Representations
• Generative Models
• Graph Analysis

Part 3: Doing Things with Networks

• Community Detection
• Network Diffusion
• Next Steps

• What is Network Science?
• Uses of Networks
• Problem Context

The burgeoning field of computer science has shifted our view of the physical world from that of a collection of interacting material particles to one of a seething network of information. In this way of looking at nature, the laws of physics are a form of software, or algorithm, while the material world-the hardware-plays the role of a gigantic computer.

• P.C.W. Davies, from 'Laying Down the Laws', New Scientist. In Clifford A. Pickover, Archimedes to Hawking: Laws of Science and the Great Minds Behind Them (2008), 183.

A graph is composed of vertexes and edges: G = (V, E). The vertexes represent things and the edges pair-wise relationships.

Complex networks may be considered in the following ways:

• Mathematical Objects: Graph Theory/Network Theory.
• Models: Network Science.
  • Structural: Where graph structure is the target of modeling (partitioning, circuits, paths).
  • Mechanistic: Where graphs are a mechanism of some process (e.g. synchrony, diffusion, inference).

• Graph Types and Representations
• Generative Models
• Graph Analysis

• Simple graphs are graphs without multiple edges or self-loops.
• Directed graphs (digraphs) have edges with directions (e.g citation network, WWW).
• Weighted graphs have an associated weight on each edge (e.g. food network with proportion of predation on edge, ARD with count of txns on edge).
• Bipartite graphs have two types of vertex that may only connect to a differing type (e.g. affiliation network, ARD).

The simple graph is composed of vertices and edges that can be represented as an edge list:

E(g)

Edge sequence:

[1] B -- A
[2] C -- B

Or an adjacency matrix which represents which vertices are adjacent to which other vertices.

get.adjacency(g)

3 x 3 sparse Matrix of class "dgCMatrix"
  A B C
A . 1 .
B 1 . 1
C . 1 .

The edge sequence is directed in the following way:

E(g)

Edge sequence:

[1] A -> B
[2] B -> C

Note the asymmetry of the adjacency matrix:

get.adjacency(g)

3 x 3 sparse Matrix of class "dgCMatrix"
  A B C
A . 1 .
B . . 1
C . . .

In addition to the edge sequence structure, the weighted graph has a vector of weights applied to its edges:

E(g)$weight

[1] 6 3 1

Edge sequence:

E(bg)

Edge sequence:

[1]  Group1 -- A     
[2]  Group2 -- A     
[3]  Group1 -- B     
[4]  Group3 -- B     
[5]  Group1 -- C     
[6]  Group3 -- C     
[7]  Group2 -- D     
[8]  Group4 -- D     
[9]  Group3 -- E     
[10] Group4 -- E     

Adjacency matrix (V x V):

get.adjacency(bg) 

9 x 9 sparse Matrix of class "dgCMatrix"
       A B C D E Group1 Group2 Group3 Group4
A      . . . . .      1      1      .      .
B      . . . . .      1      .      1      .
C      . . . . .      1      .      1      .
D      . . . . .      .      1      .      1
E      . . . . .      .      .      1      1
Group1 1 1 1 . .      .      .      .      .
Group2 1 . . 1 .      .      .      .      .
Group3 . 1 1 . 1      .      .      .      .
Group4 . . . 1 1      .      .      .      .

An incidence matrix represents the relationship between two classes of objects: V x G

get.incidence(bg)

  Group1 Group2 Group3 Group4
A      1      1      0      0
B      1      0      1      0
C      1      0      1      0
D      0      1      0      1
E      0      0      1      1

• Random graphs are the result of vertexes associating with one another randomly and with equal chance (e.g. “buttons and Strings”).
• Scale-free network: are the result of preferential attachment or fitness processes, where some vertexes accumulate the majority of associations as a result of having many associations (e.g. WWW).
• Small-world network are the result of processes where vertexes are more likely to be associated with vertexes that share common associations i.e. “friends of friends” (e.g. friend networks).
• n-Regular network are the result of a process that creates a repeating structure (e.g. lattice).