Networks

Chain networks consist of a set of nodes and a sequence of edges between them connect them into a single chain.

chain ={}
for i in range(n-1):
    make_link(chain, i, i+1)
0——–0——–0——–0——–0
n1 e1 n2 e2 n3 e3 n4 e4 n5   – nodes (n), edges (e) = n-1
Ring network –  complete the loop

ring={}
n= 5
for i in range(n):
    make_link(ring, i, (i+1)%n)
len(ring) #nodes
sum([len(ring[node]) for node in ring.keys()])/2 #edges
0—0—0—0—0
|——e5———|
5 nodes and 5 edges
Grid Network –  sort of street-wise if this was a grid-based city.

import math
grid={}
n = 256
sn = int(math.sqrt(n))
for i in range(sn):
    for j in range(sn):
        if (i<sn-1): make_line(grid,(i,j),(i+1,j))
        if (j<sn-1): make_line(grid,(i,j),(i,j+1))

print len(grid) #nodes
print(sum(len(grid[n]) for n in grid.keys()))/2 #edges

256 nodes arranged in a square,
How many total edges do we have in the graph? 480 (240+240)
formula is (apply for square, n nodes, n is perfect square).
= 2* sqrt(n) (sqrt(n)-1) = 2* n – 2(sqrt(n)) = 2* 256 – 2 *(sqrt(256))
= 512 – 32 = 480

0—0—0—0
|   |   |   |
0—0—0—0
|   |   |   |
0—0—0—0
|   |   |   |
0—0—0—0
|   |   |   |
0—0—0—0
= 20 nodes, 31 edges (15+16)
Planar Graphs – the edges don’t cross. Every region in a planar graph2_8_planer_graph has to be encapsulated,has to be bounded, by at least three edges for it to be a region.Example – five nodes and five edges.
Regions ar2_9_planer_graph_regionse kind of areas that are boxed off in the graph, plus the region outside of the graph.
n(nodes) – m(edges) + r(regions) = 2 = > Euler formulaEuler formula proof2_10_planer_graph_proof

 

 

Complete graph (also known as a clique on n-nodes) – Every node is connected to every other node, and you get very pretty star patterns if you fill these in.

# Find number edges in a complete graph on n nodes? 
def clique(n):
    return n*(n-1)/2

complete={}
def complete_graph(n):
    for i in range(n):
        for j in range(n):
            if (i<j): make_link(complete,i,j)
    
n = 5
print clique(n)
complete_graph(n)
print complete
2_12_complete_graph
Hypercube – for any number of nodes as long as that number of nodes is a power of 2.4 nodes = 22 (square), every node has a label, that label is a bit pattern.
Number for each of the nodes, from 0 to n – 1 (00, 01, 10, 11), then connect two nodes if their bit patters differ in exactly one place. Connect 11-01,00-10 because of 1st bit difference, 10-11,00-01 because of 2nd bit difference.2_12_hypercubesHypercube for n = 16, interesting trick to make hypercube, take two hypercubes on 8 nodes (cube). Add a leading “0” bit (in font of ) in the 1st hypercube & add a leading “1” bit in the 2nd hypercube. Now connect the corresponding corners of these two cubes, this is a 4-dimensional cube, also known as a hypercube.Keep extending this over and over again, like 5-bit patterns, 6-bit patterns, 7-bit patterns. Each time connecting two hypercubes of the previous size, extending them and then connecting the corresponding vertices.
00      01
0——-0
|        |
|        |
|        |
0——-0
10      11Hypercube on eight nodes (cube) – number the nodes from 0 to 7 in their binary bit patterns. Then connect two nodes if they differ in exactly one bit place.How many edges are there in an n-node hypercube? O(n log n).Explanation, take square hypercube (2-bit patterns), in general the number of bits in the label of a node and then hypercube with n edges is log n. So that means the degree of each node is log n => n times log n. But double counted again, 00 node is connected to 01 & 10, 01 is also connected back to 00 & 01 by the same bit pattern.So exact answer is 1/2 n log n, in Big Theta O, we can ignore the 1/2, O(n log n).
2_14_tree graphTree Graph – has two properties, the graph must be connected,and the graph doesn’t have any cycles or loops.
2_22_tree
Randomly Generated Graphs (Erdos – Renyi model) – Some graph with n nodes, some probability p,(call the connectivity probability). Steps.
1)Generate a set of n nodes with no edges at all.
2)for each node pair i, j, connect i,j with probability p. (loop through all possible pairs of nodes i,j, connect i, j, but only connect them after flip a coin that comes up heads with probability p. If it does come up heads, connect the pair. Otherwise, don’t.).2_15_erdos_renyi_model_1In Erdos-Rényi each edge is added independently. Researchers have found, however, that these kinds of randomly generated graphs don’t seem to match very well the kinds of social network graphs(facebook and twitter) that you see in practice in the real world.For example, in facebook it is more likely that two of your friends are connected than one of your friend and another random person in the network. Also, in twitter it is more likely that you follow someone who has a huge following than someone who doesn’t (also known as “rich get richer”). Clearly, this indicates that the edges are not independent.
2_16_Recursively Generated GraphsRecursively Generated Graphs
1) Start with a set of n nodes,
2) Create a graph (1st sub graph) on half of the nodes recursively .
3) Create a graph (2nd sub graph) on the other half of the nodes recursively.
4) Generate some edges that connect up between these two smaller (sub) graphs,
5) Return the graph.Recurrence Relation (it’s linear)

from random import choice
def makeG(n, freeNodes):
    if n == 2:
        n1 = choice(freeNodes)
        freeNodes.remove(n1)
        n2 = choice(freeNodes)
        freeNodes.remove(n2)
        return [(n1, n2)]
    binList = (0,1)
    G1 = makeG(n/2, freeNodes)
    G2 = makeG(n/2, freeNodes)
    n3 = choice(G1)[choice(binList)]
    n4 = choice(G2)[choice(binList)]
    G1.extend(G2)
    G1.append((n3, n4))
    return G1

print makeG(8, range(8))

#create graph G1, create graph G2. Pick a random node i1, 
#pick another random node i2, and link them together. 
def makeG(n): 
    if n == 1: return a single node 
    G1 = makeG(n/2) 
    G2 = makeG(n/2) 
    for i in range (log(n)): 
        i1 = random node from G1 
        i2 = random node from G2 
        make_link(G,i1,i2)

2_17_Recurrence Relationwhy the depth is log(n)? The top level node denotes ‘n’. At each subsequent level, the value of the node decreases by half, the last level node is 1. So from ‘n’ come down to 1 by halving. There are log(n) such halving required.

For example take the number 16 and log(16)=4, 16/2 = 8 # 1st halving, 8/2 = 4 # 2nd halving, 4/2 = 2 # 3rd halving, 2/2 = 1 # 4th halving

2_20_Tangled Hypercube_1Tangled Hypercube
def makeG(n):
if n == 1: return a single node
G1 = makeG(n/2)
G2 = makeG(n/2)
i1 = list of nodes of G1 in random order
i2 = list of nodes of G2 in random order
for i in range (n/2): make_link(G,i1[i],i2[i])
return G
Star network – is a network that has a single node in the center that is connected to all the rest of the nodes in the graph directly. So, here’s a star network with five nodes.

import math
def star_network(n):
    # return number of edges
    return n-1

def graph(n):
    if n == 1: return 0
    return 2*graph(n/2) + math.log(n)
n=16
star_network(n)
graph(n)
  2_231_star
2_26_combination_lock

# Generate a combination lock graph given a list of nodes
def create_combo_lock(nodes):
    G = {}
    for i in nodes:
        if (i>0):
            make_link(G, i, 0)
        make_link(G, i, (i+1)%len(nodes))
    return G
print create_combo_lock(range(5))
# {0: {1: 1, 2: 1, 3: 1, 4: 1}, 1: {0: 1, 2: 1}, 
#2: {0: 1, 1: 1, 3: 1}, 3: {0: 1, 2: 1, 4: 1}, 4: {0: 1, 3: 1}}
X Y X subset of Y Y subset of X Both Neither
Stars Trees Yes
Planar Graphs Trees Yes
Trees Rings Yes
Rings Chains Yes
Chains Trees Yes
Hybercubes Rings yes
Grids Chains Yes
Planar Graphs Hybercubes Yes
Recurrence Graphs Edge growth
T(n)=2T(n/2)+1 Tree,Chain O(n)
T(n)=2T(n/2)+O(n2) Clique,Dense graph O(n2)
T(n)=2T(n/2)+O(n) Hybercube,Tangles Hybercube O(n log n)

def make_link(G, node1, node2):
    if node1 not in G:
        G[node1] = {}
    (G[node1])[node2] = 1
    if node2 not in G:
        G[node2] = {}
    (G[node2])[node1] = 1
    return G

Propertie of social networks
1.Short paths between arbitrary nodes in the graph. example
small worlds (Me-> x, Me -> y => xy, degrees of separation (any person in the US was just 5 or 6 steps away from any other)
2.cliquish, which means they exhibit a high clustering coefficient.

Cique Ring Balanced Tree Hypercube
Degree Path Degree Path Degree Path Degree Path
0(1) yes yes yes
0(log n) yes yes yes
0(n) yes yes

Clique, each node is connected to each of the other nodes. So the degree is linear in the number of nodes.
Every node is connected to every other node. So the path you can always get directly from one node to any other node. (very small world – school) [X]

Ring, the degree in a ring is always 2. All the nodes have a degree of 2. So it’s a constant degree.
Some of the nodes are really nearby but some of them you have to go all the way to the other side to get to them and that could be as big as the number of nodes N divided by 2 because it’s the opposite side. After you get further and further and further, you start to get closer again. So the path link is actually linear in this case. []

Balanced tree, So the degree here, well a node might have a parent and two children. The root node has a degree of 2 and all the leaves have a degree of 1, so it’s never more than 3. No matter how many nodes were in the graphs so the degree is constant.
Any node can get to any other node by going up to the root and then back down to the other node you want to get to. Getting up to the root takes logarithmically not many steps. And then going back down also takes logarithmically not many steps. So it’s like two log n but that’s actually a pretty short path for a big graph.
/\
/\/\
Hypercube, each node is numbered with log n bits and it’s connected to all the other nodes in the network. The degree is a big data of log n.
So let’s imagine we want to get from some node and here’s its label 010 to some other node and here’s its label 111. We know in one hop we can go from 010 to 110. And then in one more hop we can go from 110 to 111. In fact, to go from any node in the hypercube to any other node in the hypercube, all you have to do is go through the bit positions one at a time and to reverse the corresponding edge if the source and the target differ in that bit position. So in at most log n hops we can go from any position in this hypercube to any other position.
So again pretty short paths.
010
|
110
|
111

Advertisement

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: