#12 Page Rank & Collatz Conjuncture
Think clearly.
Code confidently.
A focused, student-friendly guide to the Collatz Conjecture, PageRank, graph terminology, and NetworkX implementations—with code snippets, quick revision tables, and a self-test.
Collatz Conjecture (3n + 1 Problem)
A simple rule-based sequence with an unsolved mathematical question.
Start with any positive integer n. Repeatedly apply the even or odd rule. The conjecture states that every positive integer eventually reaches 1, although a general proof is still unknown.
while n != 1. Otherwise, continuing the rules from 1 creates the cycle 1 → 4 → 2 → 1.Algorithm in plain English
- Read a positive integer
n. - While
nis not 1, test whether it is even. - If even, replace it with
n // 2; otherwise replace it with3*n + 1. - Count each transformation and stop when
n = 1.
Sequence tracing & step counts
The starting number's size does not directly determine the number of steps.
Example A — starting number n = 7
Example B — starting number n = 256
| Starting n | Observation | Takeaway |
|---|---|---|
| 7 | Sequence rises and falls before reaching 1. | A small input can take many transformations. |
| 256 = 28 | Repeated halving reaches 1 quickly. | A larger input can take fewer transformations. |
Computer simulations can test many starting values, but testing alone does not prove that every positive integer eventually reaches 1.
PageRank: the central idea
Ranking web pages by considering both links and the importance of the linking pages.
PageRank is a link-analysis algorithm associated with web search. It does not simply count incoming links; it also considers the importance of the pages providing those links.
Applications: web-page ranking, citation networks, social networks, and other systems represented as linked nodes.
Graph terminology & NetworkX graph types
Represent real-world relationships as nodes and edges.
| Term | Meaning | Example |
|---|---|---|
| Node / vertex | An entity in the network. | Web page, person, research paper |
| Edge | A connection between entities. | Hyperlink, citation, transaction |
| Undirected graph | Edges have no direction; connection is mutual. | Railway links, friendship network (simplified) |
| Directed graph (DiGraph) | Edges run from source to target. | A web page links to another page |
| In-edge | An edge entering a node. | Incoming links to page B |
| Out-edge | An edge leaving a node. | Links from page B to other pages |
| Sink node | A node with no outgoing edges. | A page with no outgoing links |
Common built-in graph generators
| Function | Graph shape / purpose |
|---|---|
nx.barbell_graph(m1, m2) | Two complete groups joined by a path. |
nx.complete_graph(n) | Every node connects to every other node. |
nx.cycle_graph(n) | Nodes form a closed cycle. |
nx.ladder_graph(n) | Two parallel paths connected like ladder rungs. |
nx.path_graph(n) | A simple linear path. |
nx.star_graph(n) | A central hub connects to n outer nodes; total nodes = n + 1. |
nx.wheel_graph(n) | A hub connected to nodes in a cycle. |
nx.gnp_random_graph(n, p) | Random graph where edges are added with probability p. |
PageRank calculation methods
Understand the intuition, the steps, and how sinks are handled.
A. Random Walk method
- Initialize each node's visit counter to zero.
- Choose an initial node at random and count the visit.
- Find the current node's outgoing neighbours.
- If it has neighbours, choose one at random and move there.
- If it is a sink, choose a node randomly from the whole graph.
- Repeat many times; normalized visit frequencies estimate node importance.
B. Points Distribution method
- Give each node an initial score (for example, 100 points).
- Each node with outgoing edges divides its points equally among its outgoing neighbours.
- Each target sums the shares it receives.
- Repeat the redistribution for many rounds and inspect the scores.
Convergence
Repeated iterations may settle into stable scores. Exact behavior depends on graph structure and the update rules. NetworkX's built-in nx.pagerank(G) uses a standard PageRank formulation with damping and dangling-node handling, so it may not match a simplified custom algorithm exactly.
Python & NetworkX lab
Core syntax to recognize and reproduce in practical or theory exams.
1. Collatz function
def check_numb(numb):
iterations = 0
while numb != 1:
if numb % 2 == 0:
numb = numb // 2
else:
numb = 3 * numb + 1
iterations += 1
print("Final number:", numb)
print("Iterations taken:", iterations)
check_numb(12)
check_numb(20)This version counts transformations (loop iterations). For positive integer input, integer division // keeps the result as an integer.
2. Create a directed graph and inspect edges
import networkx as nx
G = nx.DiGraph()
G.add_nodes_from(range(5)) # Nodes 0, 1, 2, 3, 4
G.add_edge(1, 2) # Directed edge 1 -> 2
G.add_edge(3, 4) # Directed edge 3 -> 4
out_edges = list(G.out_edges(1))
in_edges = list(G.in_edges(2))
print("Outgoing:", out_edges)
print("Incoming:", in_edges)3. Random walk PageRank approximation
import networkx as nx
import random
G = nx.gnp_random_graph(10, 0.5, directed=True)
nodes = list(G.nodes())
x = random.choice(nodes)
visits = {node: 0 for node in nodes}
visits[x] += 1
iterations = 100_000
for _ in range(iterations):
neighbours = list(G.neighbors(x))
if not neighbours: # Sink node
x = random.choice(nodes) # Random jump
else:
x = random.choice(neighbours)
visits[x] += 1
total = sum(visits.values())
approx = {node: count / total for node, count in visits.items()}
print("Random-walk visit frequencies:", approx)
print("NetworkX PageRank:", nx.pagerank(G))4. Built-in PageRank and edge-list file
import networkx as nx
import matplotlib.pyplot as plt
G = nx.read_edgelist(
"page_rank.txt",
create_using=nx.DiGraph,
nodetype=int
)
nx.draw(G, with_labels=True)
plt.show()
pr_dict = nx.pagerank(G)
print(pr_dict)1 2 means an edge from node 1 to node 2.5. Points distribution example
def distribute_points(G, points):
nodes = list(G.nodes())
new_points = {node: 0 for node in nodes}
for node in nodes:
targets = list(G.successors(node))
if not targets:
new_points[node] += points[node] # Sink retains points
else:
share = points[node] / len(targets)
for target in targets:
new_points[target] += share
return new_points
points = {node: 100 for node in G.nodes()}
for _ in range(100):
points = distribute_points(G, points)
print("Points:", points)
print("Built-in PageRank:", nx.pagerank(G))The code illustrates the sink-retention rule described in the notes. It is a simplified redistribution model, not identical to the standard PageRank algorithm.
Quick revision table
Last-minute facts and syntax at a glance.
| Concept / function | Purpose / rule | Syntax or formula |
|---|---|---|
| Collatz even rule | Halve an even number | n = n // 2 |
| Collatz odd rule | Triple and add one | n = 3*n + 1 |
| Collatz stopping condition | Stop at 1 | while n != 1: |
| PageRank principle | Importance depends on incoming links and their source importance | Link analysis |
| Sink node | No outgoing edges | len(list(G.successors(n))) == 0 |
| Directed graph | Create a directed graph | G = nx.DiGraph() |
| Outgoing edges | Get links leaving a node | G.out_edges(n) |
| Incoming edges | Get links entering a node | G.in_edges(n) |
| Built-in PageRank | Calculate PageRank scores | nx.pagerank(G) |
| Read edge list | Load graph from a file | nx.read_edgelist(...) |
Study checklist
Self-test before the exam
Try answering without looking at the notes, then reveal the answer.
1. What is the next number after 7 in the Collatz sequence?
2. Which NetworkX class creates a directed graph?
3. What is a sink node?
4. Which function computes PageRank in NetworkX?
Comments
Post a Comment