UNIT I: Social Network Analysis
Social Network Analysis (SNA) studies relationships among entities. Nodes represent actors such
as people or computers, while edges represent relationships like friendship or communication.
Erd■s Number Project: Developed around mathematician Paul Erd■s, this measures collaboration
distance between researchers based on co-authored papers.
Centrality Measures:
• Degree centrality – number of connections.
• Betweenness centrality – bridge role between groups.
• Closeness centrality – distance to all others.
• Eigenvector centrality – influence based on important neighbors.
Balance Theory: Social relationships tend to remain psychologically balanced. For example, “friend
of my friend is my friend.”
Homophily: Similar people connect more often due to shared interests, culture, or status.
UNIT II: Random Graph Models
Random graphs connect nodes randomly. The Erd■s–Rényi model connects nodes with probability
p.
Alternative Models:
• Small-world networks: short paths and high clustering.
• Scale-free networks: few hubs with many links.
Network Growth:
• Preferential attachment – popular nodes attract more links.
• Triadic closure – friends of friends become friends.
Navigation in Social Networks:
People can reach others through short chains (six degrees).
Cohesive Subgroups:
• Cliques – fully connected groups.
• Communities – dense internal links.
Multidimensional Scaling (MDS):
A visualization method placing similar nodes closer.
Structural Equivalence:
Nodes sharing identical connections occupy similar structural positions.
Roles & Positions:
Nodes may act as leaders, brokers, or peripherals depending on connectivity.
UNIT III: Diffusion and Contagion
Network topology affects how information spreads.
Diffusion:
Spread of ideas, innovations, or diseases through networks.
Contagion:
Spread through contact such as disease or social behaviors.
Complex Contagion:
Requires multiple exposures before adoption (e.g., adopting new technology).
Percolation:
Spread occurs when connectivity exceeds a threshold.
Navigation Revisited:
Networks with local ties and shortcuts allow efficient routing and information flow.
UNIT IV: Small World Networks
Small-world experiments by Stanley Milgram showed people are connected through about six
steps.
Small-World Models (Watts–Strogatz):
Combine clustering with short path lengths.
Origins of Small World:
• Triadic closure
• Weak ties connecting distant groups
• Preferential attachment
Heavy Tails:
Few nodes (hubs) have many connections.
Small Diameter:
Even large networks have short path lengths.
Clustering:
Neighbors of a node are likely to be connected.
Erd■s–Rényi Model:
Random baseline model with predictable connectivity.
Clustering Models:
Explain tightly connected communities in real networks.
UNIT V: Network Structure & Dynamics
Important Vertices:
Influential nodes maintain connectivity and information flow.
PageRank Algorithm:
Ranks nodes based on number and importance of incoming links.
Rational Dynamics:
Individuals form links to maximize benefits and minimize costs.
Game Theory Basics:
Strategic decision-making among players; Nash equilibrium represents stable outcomes.
Coloring & Consensus:
Graph coloring prevents conflicts; consensus models agreement across networks.
Biased Voting:
Some individuals exert greater influence on group decisions.
Network Formation Games:
Individuals strategically choose connections based on costs and benefits.
Network Equilibrium:
Stable state where no participant wants to change links.
Behavioral Experiments:
Study cooperation, trust, and decision-making in networks.
Spatial & Agent-Based Models:
Simulate interactions of agents to understand epidemics, traffic, and social behavior.