UCS 813: Social Networking Analysis
Assignment
Submitted by:
Navya Sagar
102103739
BE 4th Year, COE
Submitted TO:
Dr. Nitin Saxena
Computer Science and Engineering Department
Thapar Institute of Engineering and Technology, Patiala
May 2025
1. Compute Network Statistics (Centrality & Proximity Prestige)
import networkx as nx
# Load the Karate Club graph
G = nx.karate_club_graph()
# Degree Centrality
deg_centrality = nx.degree_centrality(G)
print("Degree Centrality:", deg_centrality)
# Closeness Centrality
closeness_centrality = nx.closeness_centrality(G)
print("Closeness Centrality:", closeness_centrality)
# Betweenness Centrality
betweenness_centrality = nx.betweenness_centrality(G)
print("Betweenness Centrality:", betweenness_centrality)
# Proximity Prestige (Inverse of closeness)
proximity_prestige = {n: 1/c if c != 0 else 0 for n, c in closeness_centrality.items()}
print("Proximity Prestige:", proximity_prestige)
2. Random Walk, Hitting & Commute Time
import random
# Simulate a random walk
def random_walk(G, start, steps=10):
path = [start]
current = start
for _ in range(steps):
neighbors = list(G.neighbors(current))
current = random.choice(neighbors)
path.append(current)
return path
print("Random Walk Path:", random_walk(G, 0, 10))
# Hitting time estimation
def hitting_time(G, start, target, trials=1000):
total_steps = 0
for _ in range(trials):
current = start
steps = 0
while current != target:
current = random.choice(list(G.neighbors(current)))
steps += 1
total_steps += steps
return total_steps / trials
# Commute time = hitting_time(a, b) + hitting_time(b, a)
print("Hitting Time from 0 to 5:", hitting_time(G, 0, 5))
print("Commute Time 0 <-> 5:", hitting_time(G, 0, 5) + hitting_time(G, 5, 0))
3. Neumann Kernel (Importance & Relatedness)
import numpy as np
A = nx.adjacency_matrix(G).toarray()
I = np.eye(len(A))
alpha = 0.1 # Damping factor
# Neumann Kernel: K = (I - αA)^(-1)
K = np.linalg.inv(I - alpha * A)
# Importance (Diagonal)
importance = np.diag(K)
print("Importance Scores:", importance)
# Relatedness (Full matrix)
print("Relatedness Matrix:\n", K)
4. Markov Cluster Algorithm (MCL)
import markov_clustering as mc
# Run MCL on adjacency matrix
result = mc.run_mcl(A, expansion=2, inflation=2) # Inflation affects cluster granularity
clusters = mc.get_clusters(result)
print("MCL Clusters:", clusters)
5. PageRank Algorithm`
# Create a directed graph
DG = nx.DiGraph()
DG.add_edges_from([(0, 1), (1, 2), (2, 0), (2, 3)])
# PageRank calculation
pagerank = nx.pagerank(DG, alpha=0.85)
print("PageRank Scores:", pagerank)
6. Link Prediction Proximity Measures
from networkx.algorithms.link_prediction import common_neighbors, jaccard_coefficient
# Common Neighbors
cn = list(common_neighbors(G, 1, 2))
print("Common Neighbors (1, 2):", cn)
# Jaccard's Coefficient
jc = list(jaccard_coefficient(G, [(1, 2), (3, 4)]))
for u, v, p in jc:
print(f"Jaccard Coefficient for ({u}, {v}) = {p}")
7. Univariate Temporal Methods for Event Detection
import pandas as pd
from statsmodels.tsa.seasonal import seasonal_decompose
import matplotlib.pyplot as plt
# Simulated event data (e.g., daily tweet count)
data = pd.Series(
[5, 7, 8, 20, 7, 6, 4, 10, 25, 7],
index=pd.date_range(start='2023-01-01', periods=10, freq='D')
# Seasonal decomposition
result = seasonal_decompose(data, model='additive', period=3)
result.plot()
plt.show()
8. Influence via Reachability
# Create directed graph for reachability
DG = nx.DiGraph()
DG.add_edges_from([(0, 1), (1, 2), (2, 3), (3, 4)])
# Influence as number of reachable nodes
influence = {node: len(nx.descendants(DG, node)) for node in DG.nodes()}
print("Influence via Reachability:", influence)
