MODULE 2

Social Network Structure,

Measures & Visualization
Quick Revision Notes | CSDC8023.2

Topics Covered
• 2.1 Basics of Social Network Structure — Nodes, Edges & Ties
• 2.2 Network Measures — Degree Distribution, Density, Connectivity, Centralization, Tie Strength & Trust
• 2.3 Network Visualization — Graph Layout, Visualizing Features, Scale Issues
• 2.4 Network Analytics Tools

2.1 Basics of Social Network Structure

Key Definitions
Term Definition Example
Social Network Pattern of relationships/connections among Facebook friend network
people or organizations
SNA Social Network Analysis — uses math/stats Analyzing Twitter retweet
and graph theory to study networks patterns
Graph G=(V,E) V = vertices (nodes), E = edges Users = V, friendships = E
(connections)
Sociogram Visual representation of a network (points = Friendship map diagram
nodes, lines = ties)

Nodes & Edges

Nodes
• Entities in the network — users, organizations, brands
• Examples: Twitter users, Facebook profiles, LinkedIn companies

Edges (Ties/Links)
• Labeled — e.g., 'sister', 'colleague'
• Weighted/Valued — strength shown as a number or edge thickness
• Directed — one-way (e.g., Twitter follow: A follows B ≠ B follows A)
• Undirected — mutual relationship (e.g., Facebook friendship)

★ Directed vs Undirected
Twitter = directed edges (following is one-way). Facebook = undirected edges (friendship is mutual). In a
directed graph, order of node names matters!
Representing Networks
Term Definition Example
Adjacency List List of connected node pairs; order matters (Tom Hanks, Bill Paxton),
for directed graphs (Tom Hanks, Gary Sinise)
Adjacency Matrix Grid: 1 = edge exists, 0 = no edge; 8×8 grid for 8 nodes
symmetric for undirected
XML Format Standard data sharing format <Person><name>Tom
Hanks</name>...</Person
>

Basic Network Properties

Term Definition Example
Subnetwork Subset of nodes and/or edges from the main A friend group within
network Facebook
Singleton Isolated node with no edges A user with no
connections
Dyad Two nodes and their relationship Two friends on Facebook
Triad Three nodes A triangle of mutual
friends
Clique All nodes in a group are fully connected to Tight-knit group of friends
each other
Cluster Densely connected group (not necessarily a Online community around
full clique) a topic
Bridge Edge whose removal disconnects the graph / A person connecting two
increases components social groups
Hub Highly connected node (many edges) A celebrity with millions of
followers

Egocentric Networks
Focuses on a single central node (ego), its direct connections (alters), and ties among those alters.

Degree Type What it Includes Social Media Analogy

1-degree Ego + its direct neighbors only Celebrity + direct followers
1.5-degree Ego's neighbors + ties among Celebrity + followers who follow each
neighbors other
2-degree Ego + neighbors + neighbors' Celebrity + followers + followers-of-
neighbors followers

Paths & Connectivity

• Path — series of traversable nodes/edges; length = number of edges
• Geodesic Distance — shortest path between two nodes
• Six Degrees of Separation — average path length in global networks ≈ 6 (Milgram, 1967)
• Connected Graph — every node pair has a path between them
• Strongly Connected (directed) — directed paths exist in both directions
• Weakly Connected (directed) — connected if edge directions are ignored
• Connected Components — subgraphs that are internally connected
2.2 Network Measures
1. Degree
• Number of edges connected to a node
• In directed graphs: In-degree (incoming) + Out-degree (outgoing) = Total degree

Degree Formula
Undirected: deg(v) = number of edges at node v
In directed: separate in-degree and out-degree counts

2. Degree Distribution
• P(k) = n_k / n — fraction of nodes with degree k
• Scale-free networks follow a Power Law: P(k) ~ k^(-γ) — most nodes have few connections, few hubs
have many
• Random networks (Erdos-Renyi) follow a Poisson distribution

★ Scale-Free Networks
Real-world networks (WWW, citations, social media) are scale-free — they have a few high-degree hubs
(e.g., viral Twitter accounts). This follows power-law distribution and is explained by the Barabasi-Albert
preferential attachment model.

3. Density
Ratio of actual edges to the maximum possible edges. Low = sparse, High = dense.

Density Formula
Directed: Density = e / [n(n-1)] Undirected: Density = e / [n(n-
1)/2]
e = edges, n = nodes. Range: 0 (no edges) to 1 (fully connected)

Example: 8 nodes, 5 edges (undirected) → max possible = 28 → Density = 5/28 ≈ 0.179 (sparse)
Example: 8 nodes, 16 edges → Density = 16/28 ≈ 0.571 (dense)

★ Density in Social Media

Large networks like Twitter have very low density (~0.0001) due to scale. Small groups like family networks
have high density.

4. Connectivity
• Minimum number of nodes to remove to disconnect the graph
• Measures network resilience — higher connectivity = harder to break apart
5. Centralization
• Network-level metric — measures how unevenly centrality is distributed across the graph
• High centralization = power concentrated in very few nodes (e.g., star network)
• Low centralization = power evenly distributed (e.g., mesh network)

6. Centrality Measures
Centrality measures identify the most important or influential nodes in a network. There are 4 main types:

Type What it Measures Formula High Value Means Real Example

Degree # of direct deg(v) / (n-1) Many connections Twitter influencer
connections (popular) with many followers
Closeness How fast node 1 / avg shortest path Quick info spread Emergency
reaches others (central) broadcast hub
Betweenness How often node is Sum of σst(v)/σst Bridge/gatekeeper Broker between
on shortest paths role departments
Eigenvector Quality of Ax = λx (principal Connected to Google PageRank
connections eigenvector) important nodes
(recursive)

A. Degree Centrality — Step-by-Step

• Count direct edges of the node
• Normalize: divide by (n-1)
• Example: Node A connected to B, C, D → deg(A) = 3; n=5 → Normalized = 3/4 = 0.75

B. Closeness Centrality — Step-by-Step

• Compute shortest paths from v to all other nodes (using BFS)
• Sum all distances → compute average
• CC(v) = 1 / sum of d(v,u)
• Example: Node D paths sum = 12, avg = 12/7 ≈ 1.71 → CC(D) = 1/1.71 ≈ 0.58 (more central than Node
A: CC=0.29)

C. Betweenness Centrality — Step-by-Step

• For every pair (s,t), find all shortest paths
• For each pair, calculate: paths through v / total paths
• Sum fractions across all pairs
• Example: 5 shortest paths between two nodes, 3 pass through v → fraction = 3/5 = 0.6

D. Eigenvector Centrality — Key Points

• Importance based on the importance of your neighbors (recursive)
• Formula derived from adjacency matrix: Ax = λx
• A node with 300 important/popular friends > a node with 300 unpopular friends
• Basis of Google's PageRank algorithm
7. Tie Strength
Granovetter (1973) — ties are either Strong or Weak:

Strong Ties Weak Ties

Close, frequent, intimate contact Infrequent contact, acquaintances
Provide: trust, emotional support Provide: access to diverse/new info
Example: close family, best friends Example: LinkedIn connections, alumni

★ Strength of Weak Ties

Granovetter's key insight: Weak ties BRIDGE communities and are more valuable for job searching and
new information, because your close friends often know the same things you do!

Measuring Tie Strength: Time, emotional intensity, intimacy, reciprocal services, mutual friends, social distance,
emotional support. (Facebook study used 70+ variables: days since contact, words exchanged, etc.)

8. Trust
• Willingness to risk based on expectation of positive outcome
• Examples: lending money, sharing secrets
• Trust networks can use signed edges: + (trust), - (distrust)
2.3 Network Visualization
Graph Layout Goals
• All nodes should be visible
• Degrees should be countable
• Links should be traceable
• Clusters and outliers should be identifiable

Layout Types
Layout Description Pros / Cons
Random Nodes placed randomly Simple but offers little insight
Circular Nodes arranged in a circle Shows connections but links can cross
Grid Nodes in a structured grid Organized but doesn't reflect tie strength
Force-Directed Spring-like forces: connected nodes Best for revealing clusters; used by
attract, all repel Gephi (Fruchterman-Reingold algorithm)

Visualizing Network Features

• Node Size → represents degree or centrality (bigger = more important)
• Node Color → represents community/cluster membership
• Edge Thickness → represents tie weight/strength
• Edge Color → can represent type of relationship

Scale Issues & Solutions

Large networks (1,000+ nodes) become 'hairballs' — dense and unreadable.

Problem Solution
Too many nodes — 'hairball' effect Filter edges by weight (show only strong ties)
Dense networks obscure patterns Graph simplification — group clusters using Louvain
algorithm

★ Gephi / Cytoscape
These tools use the Fruchterman-Reingold force-directed algorithm. For large networks, the Louvain
community detection algorithm groups nodes. Example use: Visualizing Twitter hashtag networks reveals
echo chambers.
2.4 Social Media Network Analytics
Common Definitions
Term Definition Example
Network Nodes + links (the basic structure) Twitter graph
Social Network Social entities + relationships between them Facebook friendships
Social Network Site (SNS) Software platform enabling social relations Facebook, Instagram
Social Networking The act of forming and maintaining relations Posting, liking, following
SNA Methodology for studying network structures Analyzing retweet patterns

Common Social Media Network Types

• Friendship Network — mutual friend connections (Facebook)
• Follow-Following Network — directed (Twitter/X, Instagram)
• Fan Network — one-way admiration (celebrity pages)
• Professional Network — career connections (LinkedIn)
• Content Network — sharing media (YouTube)
• Co-authorship / Co-commenter — shared contributions (Wikipedia, Reddit)
• Co-like Network — users who liked the same content
• Co-occurrence Network — entities that appear together
• Hyperlink Network — web pages linked to each other

Network Classification
Dimension Types Example
Direction Directed / Undirected Twitter (directed), Facebook
(undirected)
Mode One-mode / Two-mode (bipartite) / Users-to-users / Users-to-events
Multimode
Weights Weighted / Unweighted Weighted: # of messages exchanged
Existence Explicit (default links) / Implicit Follower list vs. inferred interest graph
(constructed)

Network Analytics Tools

Tool Key Features Best For
NodeXL Free Excel add-in; connects to Facebook, Social media network collection &
Twitter, YouTube APIs; real-time data analysis
collection
UCINET Comprehensive SNA metrics; comes with Calculating all major network
Netdraw for visualization measures
Pajek Handles very large networks efficiently; open Large-scale network analysis
source
Netminer Visual analytics with drag-and-drop; good for Interactive exploration of networks
non-programmers
Gephi Open source; force-directed layouts; Visual analytics & publication-
community detection; beautiful visualizations quality graphs
Flocker Tracks Twitter retweet networks Twitter retweet mapping
Mentionmapp Maps Twitter mention networks interactively Twitter mention analysis
Quick Exam Reference
Key Formulas at a Glance
Density (Undirected)
Density = e / [n(n-1)/2]
e = actual edges, n = nodes

Density (Directed)
Density = e / [n(n-1)]

Degree Centrality (Normalized)

CD(v) = deg(v) / (n-1)

Closeness Centrality
CC(v) = 1 / Σ d(v,u) for all u ≠ v
d(v,u) = shortest path between v and u

Betweenness Centrality
CB(v) = Σ σst(v) / σst for all s≠v≠t
σst = total shortest paths from s to t; σst(v) = those through v

Degree Distribution
P(k) = n_k / n
Fraction of nodes with exactly k connections

Key Theorists to Remember

• Granovetter (1973) — Strength of Weak Ties theory
• Milgram (1967) — Six Degrees of Separation (~6 avg path length)
• Barabasi & Albert — Scale-free networks & preferential attachment model
• Erdos & Renyi — Random network model (Poisson distribution)

10-Mark Question Checklist

• Define the concept clearly with 1-2 lines
• Give the formula (if applicable)
• Walk through a numerical example step-by-step
• Provide a real-world social media example
• Compare with a related concept if asked
★ Last-minute tip
For centrality questions: Degree = popularity, Closeness = efficiency, Betweenness = control, Eigenvector =
prestige. Always link to a real social media platform example!

Module 2 Study Notes | CSDC8023.2 | Compiled for Exam Revision