Networks

Networks

Lectures cover:

• Logic
• what rules or organizations use to form connections?
• how it forms
• Structure
• what are the measures to compare networks?
• measures
• Function
• what properties emerges from the structure?
• what it does

Network Structure

• A set of nodes and edges
• edges can be undirected or directed
• Degree
• how many edges each node has on average
• node
• number of edges attached to a node
• network
• average degree of all nodes
• = 2 x Edges / Nodes
• neighbours of a node
• all other nodes connected by an edge to the node
• Theorem
• The average degree of neighbours of nodes will be at least as large as the average degree of the network
• i.e. Most people's friends are more popular than they are!
• Path Length
• definition
• Minimal number of edges that must be traversed to go from node A to node B
• Average Path Length
• Average path length between all pairs of nodes in a network
• how far it is from each node to another node

• Connectedness
• whether the entire graph is connected to itself
• definition
• A graph is connected if you can get from one node to any other
• Clustering Coefficient
• how tightly clustered are the edges
• definition
• percentage of triples of nodes that have edges between all three nodes
• What each measure tells us
• Degree
• Density of connections
• Social Capital
• A proxy for social capital
• Speed of Diffusion 
• How quickly information spreads
• Path Length
• # Flights Needed
• Social Distance
• Likelihood of information spreading
• unlikely to spread if path length is long
• Connectedness
• Markov Process - an essential precondition
• Terrorist Group Capabilities
• Connected groups are more capable
• Internet/Power Failure
• Information Isolation
• Disconnected people may not learn things
• Clustering Coefficient
• Redundancy/Robustness
• If there is a break, the network still works
• Social Capital
• Innovation adoption (triangles)
• How likely an innovation is likely adopted
• Picture = 1000 words

Network Logic

• Random attachment
• Connection procedure
• N nodes
• P probability two nodes connected
• Contextual Tipping Point
• For large N, the network almost always becomes connected when P > 1/(N-1)
• Small Worlds
• People have some percentage of "local" or "clique" friends and some percentage of random friends
• As people have more random friends, there's less clustering an shorter average path length
• Preferential Attachment
• Connection procedure:
• Node Arrives
• Probability connects to an existing node is proportional to the node's degree
• The degree distribution always results in a long tail
• A lot of nodes only have degree 1
• A handful of nodes with very high degree
• Results
• The exact network we get is path dependent
• The equilibrium degree distribution is not path dependent
• Always a long tail degree distribution

Network Function

• Micro decisions/processes when forming networks aggregates in emergent network properties
• Six Degrees
• Stanley Milgram & Duncan Watts
• Random Clique Network
• Formation Rules: Each person has
• C clique friends
• R random friends
• K-Neighbour
• All nodes that are of path length K to a node but not of any shorter path length
• Strength of weak ties