Networks¶

import pandas as pd
import networkx as nx
import matplotlib.pyplot as plt
import numpy as np
from geopy.distance import geodesic
import random
from scipy.sparse import csr_matrix, coo_matrix
import time
import copy
from scipy.io import mmread

Q1: Exploratory Data Analysis¶

Download the web-sk-2005 network dataset available here: https://networkrepository.com/web.php.

# Mount your drive so you can upload the network file
from google.colab import drive
drive.mount('/content/drive/')

Drive already mounted at /content/drive/; to attempt to forcibly remount, call drive.mount("/content/drive/", force_remount=True).

# Load the .mtx file
sparse_matrix = mmread('/content/drive/MyDrive/mid/web-sk-2005.mtx')

# Convert sparse matrix to a pandas DataFrame for inspection
df = pd.DataFrame(sparse_matrix.tocoo().toarray())
print("First five rows of the dataset:")
df.head(5)

First five rows of the dataset:

	2	3	...
0	0.0	0.0	...
1	0.0	0.0	...
2	0.0	1.0	...
3	1.0	0.0	...
4	0.0	0.0	...

5 rows × 121422 columns

We has a sparse matrix which is an efficient representation of data in which most of the elements are zero. as shown in the first 5 rows of it. Where the rows and columns correspond to the nodes, and the nonzero entries indicate edges between nodes. If there is an edge from node $i$ to node $j$, the value at position $(i, j)$ in the matrix is $1$, while all other entries are $0$.

G_not_directed = nx.from_scipy_sparse_array(sparse_matrix, create_using=nx.Graph)

# Get the number of nodes and edges
num_nodes = G_not_directed.number_of_nodes()
num_edges = G_not_directed.number_of_edges()

# Print the results
print(f"Number of nodes: {num_nodes}")
print(f"Number of edges: {num_edges}")
# this is symatric graph so when looking at the directed graph we get dupple the number of the edges.

Number of nodes: 121422
Number of edges: 334419

sparse_matrix_coo = sparse_matrix.tocoo()

# extract the row, column, and value from sparse matrix
rows = sparse_matrix_coo.row
columns = sparse_matrix_coo.col
values = sparse_matrix_coo.data

print("This is the representation of sparse matrix as it is")
print("Row indices: ", rows)
print("Column indices: ", columns)
print("Values: ", values)

This is the representation of sparse matrix as it is
Row indices:  [101377 102890 112476 ... 121394 121406 121412]
Column indices:  [     0      0      1 ... 121396 121407 121413]
Values:  [1. 1. 1. ... 1. 1. 1.]

# Get out-degree of all nodes
G = nx.from_scipy_sparse_array(sparse_matrix, create_using=nx.DiGraph)

all_out_degrees = dict(G.out_degree())
out_degree_values = list(all_out_degrees.values())  # out-degree values

plt.figure(figsize=(10, 5))
counts, bins, _ = plt.hist(out_degree_values, bins=range(0, max(out_degree_values) + 2),
                            color='skyblue', edgecolor='black', align='left')
# Find the last bin index where frequency > 10
last_nonzero_bin_index = (counts > 10).nonzero()[0][-1]
max_x = bins[last_nonzero_bin_index + 1]
plt.xlabel("Out-Degree", fontsize=15)
plt.ylabel("Frequency", fontsize=15)
plt.title("Histogram of Node Out-Degrees", fontsize=20)
plt.xticks(range(0, max(out_degree_values) + 1), rotation=60, fontsize=6)
plt.xlim(0, max_x + 1)
plt.grid(axis='y', linestyle='--', alpha=0.7)
plt.show()

No description has been provided for this image

all_in_degrees = dict(G.in_degree())  # Get in-degree of all nodes
in_degree_values = list(all_in_degrees.values())  # Extract in-degree values

plt.figure(figsize=(10, 5))

counts, bins, _ = plt.hist(in_degree_values, bins=range(0, max(in_degree_values) + 2),
                            color='skyblue', edgecolor='black', align='left')
# Find the last bin index where frequency > 10
last_nonzero_bin_index = (counts > 10).nonzero()[0][-1]
max_x_out = bins[last_nonzero_bin_index + 1]
plt.xlabel("In-Degree", fontsize=15)
plt.ylabel("Frequency", fontsize=15)
plt.title("Histogram of Node In-Degrees", fontsize=20)
plt.xticks(range(0, max(in_degree_values) + 1), rotation=60, fontsize=7)
plt.xlim(0, max_x_out + 1)
plt.grid(axis='y', linestyle='--', alpha=0.7)
plt.show()

The first histogram illustrates the distribution of out-degrees in the network, while the second represents the distribution of in-degrees. To make the histograms more visually clear, we focused on nodes with more than 10 edges (either incoming or outgoing). From the two histograms, we observe that the number of incoming edges to a node matches the number of outgoing edges from it.

Page Rank Analysis¶

def compute_pagerank(sparse_matrix, beta=0.9, tolerance=1e-6, max_iterations=1001):
    sparse_matrix = sparse_matrix.tocoo()

    # stochastic probability matrix
    column_sums = np.array(sparse_matrix.sum(axis=0)).flatten()
    column_sums[column_sums == 0] = 1  # Replace zeros with 1 to prevent division errors
    normalized_data = sparse_matrix.data / column_sums[sparse_matrix.col]
    normalized_matrix = coo_matrix((normalized_data, (sparse_matrix.row, sparse_matrix.col)), shape=sparse_matrix.shape)

    num_rows = normalized_matrix.shape[0]
    r_new = (1.0 + np.zeros([num_rows, 1])) / num_rows  # Uniform initialization
    c = (1 - beta) * r_new  # Teleportation vector
    r_prev = r_new

    # Step 3: Power iteration loop
    for i in range(1, max_iterations + 1):
        # Ensure r_prev is a column vector
        r_prev = r_prev.reshape(-1, 1)

        # Compute new PageRank vector
        r_new = beta * normalized_matrix.dot(r_prev) + c

        # Check convergence
        diff = np.sum(abs(r_new - r_prev))
        if diff < tolerance:
            print(f"Converged after {i} iterations with difference {diff:.6e}.")
            break

        # Update r_prev for the next iteration
        r_prev = r_new

    return r_new

compute_pagerank(sparse_matrix)

Converged after 104 iterations with difference 9.324176e-07.

array([[7.91947114e-06],
       [2.46666341e-06],
       [8.18048882e-06],
       ...,
       [4.12617258e-06],
       [3.65963302e-06],
       [6.89133020e-06]])

# in and out vectors
sparse_matrix_csr = sparse_matrix.tocsr()
out_degree = np.diff(sparse_matrix_csr.indptr)  # out-degree vector
sparse_matrix_csc = sparse_matrix.tocsc()
in_degree = np.diff(sparse_matrix_csc.indptr)  # in-degree vector
page_rank = compute_pagerank(sparse_matrix).flatten() # the pagerank vector

Converged after 104 iterations with difference 9.324176e-07.

nodes = np.arange(len(page_rank))  # Node indices for reference

def compute_pearson_correlation(x, y, x_label="X", y_label="Y"):
    if len(x) != len(y):
        raise ValueError("Input lists must have the same length")
    mean_x = sum(x) / len(x)
    mean_y = sum(y) / len(y)
    numerator = sum((xi - mean_x) * (yi - mean_y) for xi, yi in zip(x, y))
    denominator_x = sum((xi - mean_x) ** 2 for xi in x) ** 0.5
    denominator_y = sum((yi - mean_y) ** 2 for yi in y) ** 0.5
    denominator = denominator_x * denominator_y
    if denominator == 0:
        raise ValueError("Division by zero in correlation calculation")
    correlation = numerator / denominator
    print(f"Correlation between {x_label} and {y_label}: {correlation:.4f}")
    return correlation

def plot_and_correlate(x, y, x_label="X-axis", y_label="Y-axis", title="Scatter Plot", alpha=0.7):
    # Scatter plot
    plt.figure(figsize=(8, 6))
    plt.scatter(x, y, alpha=alpha, label=f"{x_label} vs {y_label}")
    plt.xlabel(x_label)
    plt.ylabel(y_label)
    plt.title(title)
    plt.legend()
    plt.grid()
    plt.show()

    # Compute Pearson correlation
    compute_pearson_correlation(x, y, x_label="X", y_label="Y")

plot_and_correlate(in_degree, page_rank, "In-Degree", "PageRank", "In-Degree vs PageRank")

Correlation between X and Y: 0.7048

plot_and_correlate(out_degree, page_rank, "Out-Degree", "PageRank", "Out-Degree vs PageRank")

Correlation between X and Y: 0.7048

We are calculating the correlation between the number of incoming edges to a node and its rank in the algorithm, as well as the correlation between the number of outgoing edges from a node and its rank.

The results show that the correlation between the in-degree and the PageRank vector is identical to the correlation between the out-degree and the PageRank vector. This is not surprising, as the graph is symmetric.

PageRank Analysis of Spammers¶

# Randomly select 100 pages
num_nodes = sparse_matrix.shape[0]  # Total number of nodes in the network
num_spam_nodes = 100

np.random.seed(42)
spam_nodes = np.random.choice(num_nodes, size=num_spam_nodes, replace=False)  # Select 100 random nodes

# Generate edges between every pair of the selected nodes
new_rows, new_cols = [], []
for i in spam_nodes:
    for j in spam_nodes:
        if i != j:  # Avoid self-loops
            new_rows.append(i)
            new_cols.append(j)

# Add these new edges to the sparse matrix
new_data = np.ones(len(new_rows))  # Assign a weight of 1 to each new edge

spammer_sparse_matrix = coo_matrix(
    (np.hstack([sparse_matrix.data, new_data]),
     (np.hstack([sparse_matrix.row, new_rows]),
      np.hstack([sparse_matrix.col, new_cols]))),
    shape=sparse_matrix.shape
).tocsr()

spammer_page_rank = compute_pagerank(spammer_sparse_matrix)
print(spammer_page_rank)

Converged after 104 iterations with difference 9.027335e-07.
[[7.91935564e-06]
 [2.46618905e-06]
 [8.17937773e-06]
 ...
 [4.12551149e-06]
 [3.65807292e-06]
 [6.89046689e-06]]

page_rank_befor = page_rank.flatten()
page_rank_after = spammer_page_rank.flatten()
plot_and_correlate(page_rank_befor, page_rank_after, "PageRank Before", "PageRank After", "PageRank Before vs After")

Correlation between X and Y: 0.9986

The correlation of 0.9986 between the PageRank vector before and after the spammer's changes indicates that the overall structure of the graph and the ranking of most nodes remain largely unchanged, despite the addition of 100 random edges.

This high correlation suggests that the random edges introduced by the spammer had a limited impact on the overall PageRank distribution. While local changes (such as the ranks of nodes directly involved in the new edges) may have occurred, the global ranking of nodes remained very similar. This resilience of the PageRank algorithm highlights its robustness to minor changes in the graph.

spammer_sparse_matrix_csr = spammer_sparse_matrix.tocsc()
in_degree_after = np.diff(spammer_sparse_matrix_csr.indptr)  # Compute in-degree vector
plot_and_correlate(in_degree_after, page_rank_after, "In-Degree After", "PageRank After", "In-Degree After vs PageRank After")

Correlation between X and Y: 0.6859

When a spammer added 100 random edges, the correlation between the in-degree and the PageRank vector decreased to 0.6859. This indicates that the relationship between the number of edges and the PageRank has weakened.

The drop in correlation suggests that the random edges introduced noise into the graph's structure, disrupting the natural flow of rank distribution and reducing the predictive power of in-degree and out-degree for determining a node's PageRank. This is expected because the added edges create irregularities, making the PageRank algorithm less reflective of the original graph's connectivity.

#Randomly select two distinct sets of 100 nodes each
num_nodes = sparse_matrix.shape[0]
num_spam_nodes = 100

np.random.seed(42)
spam_nodes_1 = np.random.choice(num_nodes, size=num_spam_nodes, replace=False)
remaining_nodes = np.setdiff1d(np.arange(num_nodes), spam_nodes_1)
spam_nodes_2 = np.random.choice(remaining_nodes, size=num_spam_nodes, replace=False)

new_rows = np.repeat(spam_nodes_1, len(spam_nodes_2))  # Source nodes (spam_nodes_1)
new_cols = np.tile(spam_nodes_2, len(spam_nodes_1))    # Target nodes (spam_nodes_2)
new_data = np.ones(len(new_rows))
spammer_sparse_matrix_2 = coo_matrix(
    (np.hstack([sparse_matrix.data, new_data]),
     (np.hstack([sparse_matrix.row, new_rows]),
      np.hstack([sparse_matrix.col, new_cols]))),
    shape=sparse_matrix.shape
).tocsr()

spammer_page_rank_2 = compute_pagerank(spammer_sparse_matrix_2)
print(spammer_page_rank_2)

Converged after 104 iterations with difference 9.002983e-07.
[[7.91953963e-06]
 [2.46436015e-06]
 [8.18184229e-06]
 ...
 [4.12697792e-06]
 [3.66174417e-06]
 [6.89008866e-06]]

page_rank_befor = page_rank.flatten()
page_rank_after_2 = spammer_page_rank_2.flatten()
plot_and_correlate(page_rank_befor, page_rank_after_2, "PageRank Before", "PageRank After", "PageRank Before vs After for the second strategy")

Correlation between X and Y: 0.9995

The correlation of 0.9995 between the PageRank vector before and after the second strategy (adding edges from one set of 100 random nodes to another distinct set of 100 nodes) indicates that this approach caused slightly more disruption compared to the previous strategy (where the correlation was 0.9986).

This result suggests that while the PageRank distribution remains largely stable, the directed edges between the two distinct sets have introduced more significant changes, likely because they create a directed flow of rank from one group to another. This strategy can amplify the PageRank of the target set (the second group of 100 nodes) while reducing the rank distributed to other parts of the network. However, the overall impact is still limited, as the correlation remains very high, demonstrating the robustness of the PageRank algorithm to such modifications.

spammer_sparse_matrix_csr_2 = spammer_sparse_matrix_2.tocsc()
in_degree_after_2 = np.diff(spammer_sparse_matrix_csr_2.indptr)  # Compute in-degree vector
plot_and_correlate(in_degree_after_2, page_rank_after, "In-Degree After", "PageRank After", "In-Degree After vs PageRank After for second stratigy")

Correlation between X and Y: 0.6691

The correlation of 0.6691 between the in-degree and the PageRank vector after the second strategy indicates that the relationship between the number of incoming edges to a node and its PageRank has weakened significantly compared to the original graph.

This drop in correlation suggests that the new directed edges introduced by the strategy disrupted the natural structure of the graph. Such a decrease in correlation reflects the impact of spamming strategies that manipulate connectivity to alter the importance of specific nodes artificially. It highlights how directed, targeted changes can affect the predictive relationship between graph properties and PageRank.

When comparing the two spammer strategies, the second strategy —selecting two distinct sets of 100 nodes and adding directed edges from the first set to the second set— proved to be more effective at disrupting the PageRank distribution.

The correlation between the PageRank vectors before and after the second strategy dropped slightly compared to the first strategy, indicating a greater global impact. Additionally, the second strategy significantly weakened the correlation between in-degree and PageRank, reducing it to 0.6691, whereas the first strategy had less impact on this relationship. This suggests that the second strategy was more successful at disrupting the natural relationship between the graph structure and the PageRank algorithm.

Networks¶

Q1: Exploratory Data Analysis¶

Page Rank Analysis¶

PageRank Analysis of Spammers¶

PageRank Computational Complexity¶

a¶

b¶

The psudocode of PowerMethod(B, U, V, x0, num_iterations):¶

c¶