Lecture 2 Formula Extraction + Worked Examples +

Exam Practice
Web Topology - Network Nodes and Their Characteristics
Prepared from the uploaded Lecture 2 PDF and PPTX materials.

Section What it gives you

Formula extraction All mathematical rules and formulas appearing in the lecture
materials, with variable meanings.
Worked examples Step-by-step examples for each formula so you can see exactly
how to apply it.
Exam-practice questions Many beginner, intermediate, and advanced questions. Questions
are separated from the answer key so you can practise first.
Answer key Full step-by-step solutions and short interpretation notes.

1. Lecture Formula Map

No. Formula / Rule Main exam use
1 G = (V, E) Define a graph and identify nodes/edges.
2 f(x_v) -> y_v Node classification: features to labels.
3 deg(v), k_in(v), k_out(v) Compute node degree in undirected/directed
graphs.
4 strength(v) = sum of incident weights Compute weighted node importance/activity.
5 Degree centrality C_D(v) Rank nodes by direct connections.
6 Eigenvector centrality x = (1/lambda) A x Rank nodes by importance of their
neighbours.
7 Katz centrality x = alpha A x + beta 1 Fix zero-centrality issue in acyclic/direct
graphs.
8 PageRank r = alpha P^T r + (1-alpha)v Rank pages while dividing influence by out-
degree.
9 HITS authority and hub scores Separate authority pages from hub pages.
10 Betweenness centrality Identify brokers/bridges.
11 Closeness centrality Identify nodes that can reach others quickly.
12 Node similarity: Jaccard / cosine Compare nodes by neighbours or
embeddings.
13 Feature vector x_v = [...] Design AI-ready node features.

2. Extracted Formulas with Variables and Worked Examples

Formula 1: Graph Model
Formula: G = (V, E)

Variable Meaning
G graph
V set of nodes/entities
E set of edges/relations between nodes
When to use: Use when defining any web graph: hyperlink graph, social graph, API/service graph, or knowledge graph.

Worked example: model a small web graph

 Let V = {A, B, C, D}.

 Let E = {A->B, A->C, B->D, C->D, D->B}.
 This is a directed graph because the edge A->B is not automatically the same as B->A.

Interpretation: The formula forces you to define what counts as a node and what counts as an edge before calculating any statistic.

Formula 2: Node Classification Rule

Formula: learn f(x_v) -> y_v
Lecture 2 - Web Topology Formula Practice
 Variable Meaning
x_v feature vector of node v
y_v label/target to predict for node v
f learned model mapping features to labels
When to use: Use when the task is bot detection, page topic classification, risk scoring, role prediction, or recommendation.

Worked example: bot classification

 For a user node v, choose x_v = [account_age_days, posts_per_day, out_degree, in_degree, reciprocity,
text_repetition_score].
 Possible label y_v = bot or human.
 The model f learns patterns such as high out-degree + repetitive text + 24/7 activity -> higher bot probability.

Interpretation: Good node classification depends on using features available at prediction time and avoiding leakage.

Formula 3: Degree in Undirected Graphs

Formula: deg(v) = number of incident edges on v

Variable Meaning
deg(v) degree of node v
incident edge edge touching node v
When to use: Use for simple undirected graphs such as friendship, collaboration, or mutual communication networks.

Worked example: undirected degree

 Edges: {A-B, A-C, B-C, C-D}.

 deg(A)=2 because A touches A-B and A-C.
 deg(B)=2 because B touches A-B and B-C.
 deg(C)=3 because C touches A-C, B-C, and C-D.
 deg(D)=1 because D touches C-D.

Interpretation: Degree gives a quick local popularity/activity score, but it treats all neighbours equally.

Formula 4: Directed In-Degree and Out-Degree

Formula: k_in(v) = number of edges entering v; k_out(v) = number of edges leaving v

Variable Meaning
k_in(v) incoming degree of node v
k_out(v) outgoing degree of node v
v node being measured
When to use: Use for hyperlink, follow, citation, transaction, API-call, and knowledge-graph networks.

Worked example from the lecture directed graph

 Edges: A->B, A->C, B->D, C->D, D->B.

 A: k_in(A)=0, k_out(A)=2.
 B: k_in(B)=2 from A and D; k_out(B)=1 to D.
 C: k_in(C)=1 from A; k_out(C)=1 to D.
 D: k_in(D)=2 from B and C; k_out(D)=1 to B.

Interpretation: In a hyperlink graph, high in-degree often means authority; high out-degree means the page points to many others.

Formula 5: Weighted Strength

Formula: s(v) = sum of weights on edges incident to v

Variable Meaning
s(v) strength of node v
w_uv weight of edge between u and v
incident weights all edge weights touching v
When to use: Use when edges have counts, amounts, frequencies, traffic, or intensity values.

Lecture 2 - Web Topology Formula Practice

Worked example: weighted API/service graph

 Suppose service S receives calls with weights: A->S weight 30, B->S weight 10, C->S weight 60.
 In-strength of S = 30 + 10 + 60 = 100.
 If S calls D with weight 25 and E with weight 15, out-strength of S = 25 + 15 = 40.

Interpretation: Strength can reveal heavy activity even when the number of neighbours is small.

Formula 6: Degree Centrality

Formula: C_D(v) = deg(v) or normalized: C_D(v) = deg(v)/(n-1)

Variable Meaning
C_D(v) degree centrality of node v
deg(v) degree of node v
n number of nodes in the graph
When to use: Use when the exam asks for the simplest centrality measure or asks you to rank nodes by direct connections.

Worked example: normalized degree centrality

 Graph has n=5 nodes.

 Node X has degree 3.
 C_D(X)=3/(5-1)=3/4=0.75.
 If another node has degree 1, its normalized centrality is 1/4=0.25.

Interpretation: Higher degree centrality means more direct connections, but not necessarily more strategic influence.

Formula 7: Eigenvector Centrality

Formula: x_i = (1/lambda) * sum_j A_ij x_j equivalently: A x = lambda x

Variable Meaning
x_i centrality score of node i
A_ij adjacency matrix entry
lambda eigenvalue; leading/largest eigenvalue used
x centrality vector
When to use: Use when node importance depends on being connected to important nodes, not just many nodes.

Worked example: path graph A-B-C

 Adjacency: A connected to B; B connected to A and C; C connected to B.

 For a 3-node path, the leading eigenvector is proportional to [1, sqrt(2), 1].
 So B has the highest eigenvector centrality because it is connected to both A and C.
 A and C are equal by symmetry.

Interpretation: Eigenvector centrality rewards quality of neighbours. The lecture notes warn that in acyclic directed networks it can
give all-zero scores, motivating Katz/PageRank.

Formula 8: Katz Centrality

Formula: x = alpha A x + beta 1 and x = beta (I - alpha A)^(-1) 1 x = β + α ∑(scores of nodes that point to i)

Variable Meaning
x Katz centrality vector
alpha attenuation/free parameter controlling neighbour influence
beta baseline centrality given to every node
A adjacency matrix
I identity matrix
1 all-ones vector
When to use: Use when eigenvector centrality fails because some nodes would otherwise get zero score, especially in directed or
acyclic graphs.

Worked example: path graph A-B-C with alpha=0.2, beta=1

Lecture 2 - Web Topology Formula Practice

 By symmetry, x_A = x_C = a and x_B = b.
 Equations: a = 1 + 0.2b; b = 1 + 0.2(a+a) = 1 + 0.4a. For each node i:

x = β + α ∑(scores of nodes that point to i)

 Substitute: a = 1 + 0.2(1 + 0.4a) = 1.2 + 0.08a.
 0.92a = 1.2, so a = 1.304.
 b = 1 + 0.4(1.304) = 1.522.
 Katz ranking: B highest, then A and C.

Interpretation: Katz gives every node a baseline score, so nodes do not get stuck at zero.

Formula 9: PageRank
Formula: r = alpha P^T r + (1 - alpha)v r = alpha P + (1-alpha).(1/n).1.1^T

Variable Meaning
r PageRank vector
alpha damping factor; lecture mentions Google commonly uses 0.85
P row-stochastic transition matrix from outgoing links D^(-1).A

v teleportation/personalisation vector
P^T transpose so incoming links contribute to rank
When to use: Use when ranking web pages in a directed graph while dividing a page’s influence across its outgoing links.

Worked example: one PageRank iteration

 Edges: A->B, A->C, B->C, C->A.

 Out-degrees: k_out(A)=2, k_out(B)=1, k_out(C)=1.
 Start r0=[1/3,1/3,1/3], alpha=0.85, v=[1/3,1/3,1/3]. Teleport term=(1-alpha)/3=0.05.
 PR(A)=0.05 + 0.85*(PR(C)/1)=0.05+0.85*(1/3)=0.333.
 PR(B)=0.05 + 0.85*(PR(A)/2)=0.05+0.85*(1/6)=0.192.
 PR(C)=0.05 + 0.85*(PR(A)/2 + PR(B)/1)=0.05+0.85*(1/6+1/3)=0.475.

Interpretation: C gets the largest score after one iteration because it receives links from both A and B; A’s influence is split
between B and C.

Formula 10: HITS Authority and Hub Scores

Formula: authority(i) = sum_{j -> i} hub(j); hub(i) = sum_{i -> j} authority(j)

Variable Meaning
authority(i) how valuable/trusted node i is as an information source
hub(i) how useful node i is as a pointer to good authorities
j -> i a link from node j to node i
When to use: Use for directed topic-search networks where some pages are authorities and others are hubs linking to authorities.

Worked example: HITS one update

 Directed edges: H->A1, H->A2, P->A1.

 Start hub scores h(H)=1 and h(P)=1.
 Authority update: a(A1)=h(H)+h(P)=1+1=2; a(A2)=h(H)=1.
 Hub update using these authorities: h(H)=a(A1)+a(A2)=2+1=3; h(P)=a(A1)=2.
 Before normalization, H is the better hub and A1 is the better authority.

Interpretation: HITS separates two roles: a good hub points to good authorities; a good authority is pointed to by good hubs.

Formula 11: Betweenness Centrality

Formula: C_B(v) = sum_{s != v != t} sigma_st(v) / sigma_st

Variable Meaning
C_B(v) betweenness centrality of node v
sigma_st number of shortest paths from s to t
sigma_st(v) number of those shortest paths passing through v
When to use: Use when identifying bridges, brokers, bottlenecks, HR-like connectors, airport hubs, or key routers.

Worked example: path A-B-C-D

Lecture 2 - Web Topology Formula Practice
 Consider unordered pairs not including B: (A,C), (A,D), (C,D).
 Shortest path A-C is A-B-C, so B lies on it: +1.
 Shortest path A-D is A-B-C-D, so B lies on it: +1.
 Shortest path C-D is C-D, so B does not lie on it: +0.
 Therefore C_B(B)=2 in unnormalised form.

Interpretation: B is a bridge between A and the rest of the path; removing it separates A from C and D.

Formula 12: Closeness Centrality

Formula: C_C(v) = (n - 1) / sum_{u != v} d(v,u)

Variable Meaning
C_C(v) closeness centrality of node v
n number of nodes
d(v,u) shortest-path distance between v and u
When to use: Use when measuring how quickly a node can reach all other nodes.

Worked example: path A-B-C-D

 For node B: distances to A,C,D are 1,1,2.

 Sum of distances = 1+1+2=4.
 n=4, so C_C(B)=(4-1)/4=3/4=0.75.
 For node A: distances to B,C,D are 1,2,3. C_C(A)=3/6=0.5.
 Therefore B is more central by closeness than A.

Interpretation: High closeness means short average distance to everyone else; it is sensitive to disconnected graphs.

Formula 13: Node Similarity - Jaccard and Cosine

Formula: J(u,v)=|N(u) intersect N(v)| / |N(u) union N(v)|; cos(u,v)=|N(u) intersect N(v)| / sqrt(|N(u)||N(v)|)

Variable Meaning
N(u) neighbour set of node u
N(v) neighbour set of node v
J(u,v) Jaccard similarity
cos(u,v) cosine similarity on neighbour vectors
When to use: Use for node similarity, recommendation, near-duplicate detection, and clustering.

Worked example: compare two nodes

 N(u)={a,b,c}; N(v)={b,c,d,e}.
 Intersection={b,c}, size 2.
 Union={a,b,c,d,e}, size 5.
 Jaccard=2/5=0.40.
 Cosine=2/sqrt(3*4)=2/sqrt(12)=0.577.

Interpretation: Both measure overlap, but Jaccard penalizes large unions more strongly.

Formula 14: AI Feature Vector for a Node

Formula: x_v = [numeric, categorical, text-derived, topology]

Variable Meaning
x_v feature vector for node v
numeric counts/rates such as posts per day
categorical type, language, verified status
text-derived TF-IDF or embedding features
topology degree, centrality, clustering, motifs
When to use: Use when designing features for bot detection, page classification, trust/safety, ranking, or recommendation.

Worked example: GitHub repository beginner-friendly classifier

Lecture 2 - Web Topology Formula Practice

 x_v could include: stars, forks, open issues, README length, documentation score, number of beginner labels, language, topic
tags, contributor count, recent commit activity, degree in dependency graph.
 Avoid leakage: do not use a feature that directly contains the final label, such as an official beginner-friendly tag if that is the
target.
 Mark expensive features: embeddings and graph centralities can be more expensive than simple metadata counts.

Interpretation: A good feature vector is available at prediction time, robust, explainable, and not a disguised version of the label.

Lecture 2 - Web Topology Formula Practice

3. Exam-Practice Questions - Try First
Try to answer these before checking the solution section. They cover every mathematical formula and calculation method extracted
from Lecture 2.

Q1. Graph model

A platform has users U1,U2,U3 and pages P1,P2. Users follow each other and also like pages. Define two possible graphs G=(V,E):
one homogeneous and one heterogeneous. State V and E for each.

Q2. Directed degree

For directed edges A->B, A->C, B->D, C->D, D->B, compute k_in and k_out for A, B, C, and D.

Q3. Normalized degree centrality

An undirected graph has n=7 nodes. Node X has degree 4 and node Y has degree 2. Compute normalized degree centrality for
both and rank them.

Q4. Weighted strength

A service S receives weighted calls A->S=45, B->S=15, C->S=40 and sends S->D=20, S->E=30. Compute in-strength and out-
strength of S.

Q5. Node classification features

Design x_v for predicting whether a social-media account is a bot. Give at least 8 features and identify one possible leakage feature
to avoid.

Q6. Eigenvector centrality intuition

In a path graph A-B-C, explain why B has higher eigenvector centrality than A and C. Use the vector [1, sqrt(2), 1] as the
unnormalised leading eigenvector.

Q7. Katz centrality calculation

For path A-B-C, use alpha=0.2 and beta=1. Solve Katz centrality assuming x_A=x_C=a and x_B=b.

Q8. Katz parameter concept

Explain what happens when alpha approaches 0 in Katz centrality. What happens when alpha is chosen too large?

Q9. PageRank one iteration

For edges A->B, A->C, B->C, C->A, start from r0=[1/3,1/3,1/3], alpha=0.85, uniform teleportation. Compute one PageRank iteration.

Q10. PageRank dilution

A page H has PageRank score 60. Case 1: H links to 3 pages. Case 2: H links to 30 pages. Ignoring damping/teleportation, how
much rank does each outgoing link receive in each case?

Q11. HITS update

Edges are H->A1, H->A2, P->A1. Start with hub scores h(H)=h(P)=1. Compute one authority update and then one hub update.

Q12. Authority vs hub

A page links to 20 high-quality research pages but receives no in-links. Is it more likely to have high hub score or high authority
score? Explain.

Q13. Betweenness in a path

Lecture 2 - Web Topology Formula Practice

For path A-B-C-D, compute unnormalised betweenness for B and C using unordered pairs.

Q14. Betweenness with multiple shortest paths

Suppose shortest paths from S to T are S-A-T and S-B-T. Node A lies on one of the two shortest paths. What is A’s contribution for
pair (S,T)?

Q15. Closeness in a path

For path A-B-C-D, compute closeness for A and B using C_C(v)=(n-1)/sum distances.

Q16. Closeness interpretation

Two routers have closeness 0.20 and 0.50. Which one reaches the rest of the network faster on average? Explain.

Q17. Jaccard similarity

N(u)={a,b,c,d}, N(v)={b,c,e}. Compute Jaccard similarity.

Q18. Cosine similarity

Using the same neighbour sets as Q17, compute cosine similarity.

Q19. Compare Jaccard and cosine

A has 100 neighbours, B has 110 neighbours, and they share 50 neighbours. Compute Jaccard if the union size is 160. Compute
cosine. Which is higher?

Q20. Feature vector for page classification

Design x_v for classifying pages into health, finance, sports, and education. Include content, metadata, and topology features.

Q21. Identity resolution

You see “BUE”, “British University in Egypt”, and “The British Uni Egypt”. Give 3 signals to decide whether they are the same node
and one risk of merging incorrectly.

Q22. In-degree interpretation

Give two different interpretations of high in-degree: one in a hyperlink graph and one in a social follow graph.

Q23. Centrality selection

Which centrality would you choose to find a communication bottleneck: degree, closeness, betweenness, PageRank, or HITS?
Justify.

Q24. Acyclic network issue

Why can ordinary eigenvector centrality be unsuitable for citation networks? Which lecture measure helps fix the zero-score
problem?

Q25. Full mini-exam

Given directed graph A->B, A->C, B->C, C->D, D->B: (a) compute in/out degree for each node; (b) identify one possible authority;
(c) choose one feature useful for bot detection if these were user follows; (d) explain whether PageRank should divide by out-
degree.

Lecture 2 - Web Topology Formula Practice

4. Answer Key with Step-by-Step Solutions
Q1
 Homogeneous graph example: V={U1,U2,U3}; E={follow edges between users only}.
 Heterogeneous graph example: V={U1,U2,U3,P1,P2}; E can include follows(Ui,Uj) and likes(Ui,Pk).
 The heterogeneous graph keeps multiple entity types and can support richer AI tasks.

Q2
 Edges: A->B, A->C, B->D, C->D, D->B.
 A: in=0, out=2.
 B: in=2 from A,D; out=1 to D.
 C: in=1 from A; out=1 to D.
 D: in=2 from B,C; out=1 to B.

Q3
 Normalized degree centrality is deg(v)/(n-1).
 X: 4/(7-1)=4/6=0.667.
 Y: 2/6=0.333.
 X ranks higher.

Q4
 In-strength = 45+15+40=100.
 Out-strength = 20+30=50.
 S receives more weighted traffic than it sends.

Q5
 Possible features: account_age_days, posts_per_day, burstiness, night_activity_rate, in_degree, out_degree, reciprocity,
repeated_URL_rate, profile_photo_flag, text_similarity_to_known_bots.
 Leakage feature to avoid: a moderation label or “bot_flag” produced after investigation if it is the target label.

Q6
 For path A-B-C, the leading eigenvector is proportional to [1, sqrt(2), 1].
 sqrt(2)=1.414 > 1, so B has the highest score.
 B is connected to both endpoints, while A and C each connect only to B.

Q7
 Let x_A=x_C=a and x_B=b.
 a=1+0.2b.
 b=1+0.2(a+a)=1+0.4a.
 Substitute: a=1+0.2(1+0.4a)=1.2+0.08a.
 0.92a=1.2 -> a=1.304.
 b=1+0.4(1.304)=1.522.
 Ranking: B > A=C.

Q8
 If alpha approaches 0, x = beta*1, so every node gets the same baseline score.
 If alpha is too large, the centrality can diverge or become unstable. The lecture notes state alpha must be controlled relative to
the largest eigenvalue.

Q9
 Out-degrees: A=2, B=1, C=1. Teleport term=(1-0.85)/3=0.05.
 PR(A)=0.05+0.85*(PR(C)/1)=0.05+0.85/3=0.333.
 PR(B)=0.05+0.85*(PR(A)/2)=0.05+0.85*(1/6)=0.192.
 PR(C)=0.05+0.85*(PR(A)/2+PR(B)/1)=0.05+0.85*(1/6+1/3)=0.475.
 After one iteration: A=0.333, B=0.192, C=0.475.

Lecture 2 - Web Topology Formula Practice

Q10
 Case 1: 60/3=20 rank units per outgoing link.
 Case 2: 60/30=2 rank units per outgoing link.
 This is the out-degree dilution idea in PageRank.

Q11
 Start h(H)=1 and h(P)=1.
 Authority: a(A1)=h(H)+h(P)=2; a(A2)=h(H)=1.
 Hub: h(H)=a(A1)+a(A2)=3; h(P)=a(A1)=2.
 H is the stronger hub; A1 is the stronger authority.

Q12
 It is more likely to have a high hub score.
 It points to many good authorities, but receives no in-links, so its authority score may be low.

Q13
 For B, pairs excluding B are (A,C), (A,D), (C,D). B lies on A-C and A-D, not C-D. So C_B(B)=2.
 For C, pairs excluding C are (A,B), (A,D), (B,D). C lies on A-D and B-D, not A-B. So C_B(C)=2.

Q14
 sigma_ST=2 because there are two shortest paths.
 sigma_ST(A)=1 because A lies on one of them.
 Contribution = 1/2 = 0.5.

Q15
 For A: distances to B,C,D are 1,2,3. Sum=6. C_C(A)=3/6=0.5.
 For B: distances to A,C,D are 1,1,2. Sum=4. C_C(B)=3/4=0.75.
 B is closer to the rest of the graph.

Q16
 The router with closeness 0.50 reaches the rest faster on average.
 Higher closeness means smaller total distance to other nodes.

Q17
 Intersection={b,c}, size 2.
 Union={a,b,c,d,e}, size 5.
 J=2/5=0.4.

Q18
 |N(u)|=4, |N(v)|=3, shared=2.
 cos=2/sqrt(4*3)=2/sqrt(12)=0.577.

Q19
 Jaccard=50/160=0.3125.
 Cosine=50/sqrt(100*110)=50/sqrt(11000)=50/104.88=0.477.
 Cosine is higher here because it normalizes by geometric mean rather than union size.

Q20
 Content: TF-IDF keywords, text embedding, title terms.
 Metadata: domain, language, author, recency.
 Topology: in-degree, out-degree, PageRank, neighbours’ topics, number of links from trusted domains.
 The feature vector should not include the final manually assigned topic if that is the label.

Q21
 Signals: string similarity, shared official URL/domain, same location/address, same registry ID, same social profiles.
 Risk of wrong merge: two different organizations could be collapsed into one node, corrupting metadata and AI answers.

Lecture 2 - Web Topology Formula Practice

Q22
 Hyperlink graph: high in-degree means many pages link to this page, so it may be an authority/citation target.
 Social follow graph: high in-degree means many followers, so the user may be popular/influential.

Q23
 Choose betweenness centrality.
 A communication bottleneck is a node that lies on many shortest paths between others. Degree alone may miss low-degree
bridges.

Q24
 Citation networks are often acyclic because newer papers cite older papers and edges do not loop back.
 Ordinary eigenvector centrality may give zero centrality to nodes outside strongly connected structures.
 Katz centrality helps by adding a baseline centrality term. PageRank also handles directed web-style ranking with out-degree
dilution.

Q25
 (a) Edges: A->B, A->C, B->C, C->D, D->B. A: in=0,out=2. B: in=2 from A,D; out=1. C: in=2 from A,B; out=1. D: in=1 from C;
out=1.
 (b) B or C could be possible authorities because they receive two incoming links.
 (c) For bot detection, useful features include unusually high out-degree, low reciprocity, burstiness, repeated content, or star
pattern.
 (d) Yes. PageRank divides by out-degree so a node linking to many others does not pass full importance to every target.

Lecture 2 - Web Topology Formula Practice

5. One-Page Memorization Sheet
Need to solve... Use this formula/rule Remember
Direct popularity Degree / in-degree / out-degree Counts only direct links.
Weighted activity strength = sum of weights Weights matter more than just edge count.
Quality of neighbours Eigenvector: A x = lambda x Important if connected to important nodes.
Directed/acyclic influence Katz: x = alpha A x + beta 1 Baseline prevents zero scores.
Web page ranking PageRank: r = alpha P^T r + (1-alpha)v Out-degree dilution fixes Yahoo problem.
Authorities vs curators HITS authority/hub updates Authorities are pointed to; hubs point to
authorities.
Bridge/bottleneck Betweenness Counts shortest paths through node.
Fast reach Closeness Inverse of total distance.
Similarity Jaccard / cosine Overlap of neighbours or embeddings.
AI prediction f(x_v)->y_v Features must be available at prediction time.
Source note: This workbook was prepared from the uploaded Lecture 2 PDF summary and Lecture 2 PPTX slides, including the
slide content on node identity, degree, centrality, Katz, PageRank, HITS, node features, embeddings, node classification, and
web/AI case studies.

Lecture 2 - Web Topology Formula Practice