Module 1
Networks and Society
AND
Network Measures
By: Udit Gupta
Department of AI&DS
CMR Institute Of Technology
What is Social Network Analysis (SNA)?
• Social Network Analysis (SNA) is a quantitative and qualitative methodological framework
that examines social structures through networks and graph theory.
• It maps relationships (edges) between entities (nodes) to uncover patterns of interaction,
influence, and information flow.
Components:
Nodes (Actors): Entities
individuals, organizations, websites.
Edges (Ties): Relationships
friendships, collaborations, hyperlinks.
Graph: Mathematical representation G (V, E)
where V = nodes, E = edges.
Why Study Social Networks?
Understand Social Dynamics:
• Diffusion Processes: How information, innovations, or diseases spread.
• Social Capital: Networks as resources.
• Power Structures: Centrality reveals influencers.
• Predict Collective Behavior:
• Address Real-World Problems:
• Public Health: Targeting super-spreaders to curb epidemics.
• Counterterrorism: Disrupting dark networks by isolating brokers.
• Organizational Efficiency: Optimizing team communication in corporations.
• Digital Age Imperatives:
• Online platforms (Facebook, Twitter) generate massive relational data.
• AI/ML integration enables predictive SNA
Applications of Social Network Analysis
• Sociology & Anthropology:
• Community Detection: Identifying subgroups (e.g., cliques in schools).
• Social Support Systems: Mapping kinship networks in indigenous tribes.
• Business & Economics:
• Organizational Network Analysis (ONA): - Optimizing workflows (e.g., email
traffic analysis).
• Identifying innovation brokers in R&D teams.
• Market Research: Brand ambassador detection via influencer centrality.
• Public Health:
• Epidemiology: Contact tracing networks.
• Mental Health: Peer effects in substance abuse interventions.
• Technology & Cybersecurity:
• Internet Topology: AS-router networks for robustness analysis.
• Botnet Detection: Isolated clusters of malicious bots.
• Politics & Security:
• Counterinsurgency: Mapping terrorist cell hierarchies.
• Policy Implementation: Stakeholder networks in climate change agreements.
Social Network Analysis: Preliminaries
and Definitions
• Nodes (or Vertices): These are the individual entities within a network, such as people,
organizations, or other social units.
• Edges (or Ties): These represent the connections or relationships between the nodes.
They can be binary (indicating the presence or absence of a relationship) or weighted
(indicating the strength or intensity of the relationship).
• Network: The set of nodes and edges that represent the social structure being analyzed.
• Degree: The number of connections a node has. In a directed network, nodes can have
both in-degree (incoming connections) and out-degree (outgoing connections).
• Centrality: This refers to the relative importance of a node within a network. Different
measures of centrality include degree centrality, betweenness centrality, and closeness
centrality.
• Clustering: The tendency of nodes to form clusters or groups within a network,
indicating the presence of sub-communities or cohesive subgroups.
• Density: The proportion of connections in a network relative to the total possible
connections. It indicates the degree of interconnection among the nodes.
• Homophily: The tendency for individuals with similar attributes or characteristics
to be connected within a network.
• Social Capital: The resources embedded within social networks, including
information, support, and access to opportunities.
• Ego Network: The network immediately surrounding a focal node, including the
focal node and its direct connections.
Types of Networks: Structural Classifications
Networks vary by directionality, weight, node homogeneity, and temporality.
Directed vs. Undirected Networks
Undirected Networks:
• Edges have no direction
(e.g., Facebook friendships, co-authorship).
• Adjacency Matrix: Symmetric (Aij=Aji).
• Metrics: Degree centrality (total connections).
Directed Networks (Digraphs):
Edges indicate direction (e.g., Twitter follows, citation networks).
Adjacency Matrix: Asymmetric (Aij≠Aji).
Metrics:
In-Degree: Ties received (popularity).
Out-Degree: Ties initiated (influence).
Ego Networks
A focal node (ego), its direct neighbors (alters), and ties among alters.
• Ego: Central node of interest.
• Alters: Nodes directly connected to the ego.
• Ego-Alter Ties: Relationships between ego and alters.
• Alter-Alter Ties: Connections among alters.
Two-Mode Networks (Bipartite Networks)
Two disjoint node sets (Mode A and Mode B), with edges only between sets
e.g., actors & movies, authors & papers.
Dynamic vs. Static Networks
Static Networks:
Snapshot of ties at a single time point.
Use Cases: Cross-sectional studies
e.g., organizational structure.
Limitations: Ignores evolution, temporal causality.
Dynamic (Temporal) Networks:
Networks evolving (edges/nodes added/removed).
Representations:
Discrete Time Slices: Gt1, Gt2,…, Gtn.
Continuous Time: Event logs.
Relational Events: Time-stamped interactions
e.g., messages.
Three Levels of Social Network Analysis
• Micro-level: Analysis of individual nodes (e.g., ego networks).
• Ego networks provide a detailed, personalized view of an individual's social world, rather
than the entire network structure.
• Ego: The central individual whose network is being analyzed.
• Alters: The direct connections or relationships of the ego within the network.
• The analysis examines the quality, strength, and diversity of the ties between the ego and
its alters, rather than just their existence.
• Hierarchical Structure:
• Ego networks often show a hierarchical structure, with contacts organized in layers, where the
innermost layer represents strong ties and outer layers represent weaker ties.
• Applications
• Understanding Individual Behavior:
• How an individual's network position influences their career, health, or adoption of new
behaviors and technologies.
• Information Diffusion:
• Analyzing tie strength and network layers helps understand how information spreads, as seen
in the
• Marketing:
• Understanding an influencer's personal network can optimize targeted advertising strategies.
• Public Health:
• Studying how personal networks affect health behaviors and outcomes.
• Meso-level: Group or community structures within the network.
• The meso-level in network analysis refers to the examination of communities, sub-
networks, and organizations that exist within larger networks.
• Macro-level: Overall structure and properties of the entire network
• Macro-level analysis of a network examines its overall structure and properties, such
as network density, path length, degree distribution, clustering coefficient, reachability,
and transitivity, to understand network-wide dynamics like information flow and the
presence of hubs and peripheral nodes.
Macro-Level Network Properties
•Density:
•Measures the proportion of actual connections to potential connections within the
network.
•Path Length:
•Refers to the average distance between nodes, which influences information flow and the
"small-world" phenomenon.
•Degree Distribution:
•Describes the number of nodes that have a certain number of connections. Scale-free
networks have a few high-degree hubs and many low-degree nodes.
•Clustering Coefficient/Transitivity:
•Measures the tendency of nodes to form clusters or triangles, which contributes to small-
world properties and can indicate information diffusion or social cohesion.
• Reachability:
• Involves the distribution of geodesic distances, showing how easily or quickly nodes
can reach each other through the network.
• Hierarchy:
• Examines the extent of stratification or levels of authority within the network.
• Small-World Property:
• Characterized by short average path lengths and high clustering coefficients, enabling
efficient information spread.
• Scale-Free Property:
• A property of networks with power-law degree distributions, resulting in a few highly
connected "hubs" and numerous less-connected nodes.
Network Basics
• Degree: Number of connections a node has.
• Path: Sequence of edges connecting nodes.
• Diameter: Longest shortest path in the network.
• Density: Ratio of actual to possible connections.
• Components: Subsets of connected nodes.
Node Centrality
Degree Centrality: Number of direct connections.
Betweenness Centrality: Frequency of a node appearing on shortest paths.
Closeness Centrality: Average length of shortest paths from the node
to all others.
• Eigenvector Centrality: Importance based on connections to high-scoring
nodes.
Assortativity
• Measures the tendency of nodes to connect to similar nodes.
• Assortativity tells us whether a network is made of similar nodes
sticking together or different nodes linking up.
• Types:
• Degree Assortativity (similar degree values): Do nodes with similar degree
(number of connections) tend to connect?
• Attribute Assortativity (similar attributes): Do nodes with similar attributes
(age, profession, location, etc.) tend to connect?
• Positive assortativity: similar nodes connect.
• Negative assortativity: dissimilar nodes connect.
Problem:
Consider a small undirected network with 4 nodes and the following edges:
•Edge 1: Connects nodes with degrees 3 and 2
•Edge 2: Connects nodes with degrees 3 and 2
•Edge 3: Connects nodes with degrees 3 and 1
•Edge 4: Connects nodes with degrees 2 and 2
Calculate the Pearson correlation coefficient (rxy) to determine if the network is assortative, disassortative, or non-
assortative.
Similarity
Jaccard similarity
•Focus: Jaccard similarity measures the overlap between two sets. In the context of nodes, it compares the set of
neighbors of two nodes.
•Formula: Jaccard Similarity (A, B) = |N(A) ∩ N(B)| / |N(A) ∪ N(B)|, where N(A) and N(B) represent the sets of
neighbors of nodes A and B, respectively.
•Interpretation: The Jaccard similarity score ranges from 0 to 1. A score of 1 indicates that the two nodes have
identical sets of neighbors, while 0 means they share no common neighbors
Cosine similarity
•Focus: Cosine similarity measures the similarity in the direction or orientation of two vectors, ignoring
differences in their magnitude or scale. In node similarity, nodes are represented as vectors reflecting their
connections or attributes.
•Formula: Cosine (A, B) = (A ⋅ B) / (||A|| × ||B||), where A and B are the vectors representing the nodes, A ⋅ B is
their dot product, and ||A|| and ||B|| are their magnitudes.
•Interpretation: The cosine similarity score ranges from -1 to 1. A score of 1 means the vectors are perfectly
aligned (highly similar), 0 indicates they are orthogonal (no directional similarity), and -1 signifies they are
diametrically opposed (completely dissimilar).
•Jaccard Similarity:
Set A = {0, 1, 2, 5, 6}
Set B = {0, 2, 3, 4, 5, 7, 9}
Intersection (A ∩ B) = {0, 2, 5}
Union (A ∪ B) = {0, 1, 2, 3, 4, 5, 6, 7, 9}
Jaccard Similarity = |A ∩ B| / |A ∪ B| = 3 / 9 = 0.333
•Cosine Similarity:
Vector A = [3, 4]
Vector B = [3, 3]
Dot Product (A ⋅ B) = (3 * 3) + (4 * 3) = 9 + 12 = 21
Magnitude of A (||A||) = √(3² + 4²) = √(9 + 16) = √25 = 5
Magnitude of B (||B||) = √(3² + 3²) = √(9 + 9) = √18 ≈ 4.24
Cosine Similarity = (A ⋅ B) / (||A|| × ||B||) = 21 / (5 × 4.24) ≈ 0.99
Degeneracy
In Social Network Analysis (SNA), degeneracy refers to the existence of multiple, structurally
distinct ways to achieve the same functional outcome or state within the network. Unlike
redundancy, where identical elements perform the same function, degeneracy involves different
components or pathways contributing to a single, common goal, offering adaptability and
resilience to the system.
What Is Core Number?
•The core number (or coreness) of a node is the highest-order k-core to which the node belongs
in the network.
•A k-core is a maximal subgraph in which every node has at least k connections (degree ≥ k)
within that subgraph.
•For any node:
o If it belongs to the k-core, but not to the (k+1)-core, its core number is k.
o This tells us how deeply embedded a node is within dense regions.
Degeneracy
What Is Core-Periphery Structure?
Definition:
A network organization where there is:
o Core: a densely connected group of nodes (shown as black dots), where almost
every core member is connected to others in this region.
o Periphery: The surrounding nodes (gray dots), which are more sparsely and
randomly connected, and mainly link to the core rather than to each other.
•Core (circled in red)
Represents the "heart" of the network, tightly and mutually connected.
Examples: executive committee in an organization, highly collaborative research team,
key router cluster in an internet backbone.
•Periphery:
Nodes around the core have looser, weaker, and often fragmented connections; these
nodes are dependent on the core for communication or access.
•Features and Significance
Dense core: Maximizes resilience, influence, and coordination among core members.
Scrambled periphery: Peripheral nodes are less important individually and rely on core
for connectivity or information.
Real Networks: Social systems (elite cliques with many followers), transportation
systems (major hubs vs minor stops), the web (popular portals vs small blogs).
In summary, core-periphery structure shows how networks are organized into
influential, highly connected centers with peripheral, less connected components,
shaping the network’s efficiency and robustness.