Worksheetssocial-network
Total questions: 70
Worksheet time: 35mins
Name
Class
Date
1.
In a bipartite graph edges connect:
a)
Any nodes in the same set
b)
Nodes across two disjoint sets
c)
Only weighted nodes
d)
Only directed nodes
2.
An edge list primarily stores:
a)
A dense boolean table of adjacencies
b)
Pairs (u v) (plus optional attributes)
c)
For each node a dictionary of neighbors
d)
Node features only
3.
For a very sparse network that grows via edge insertions the default-practical structure is:
a)
Adjacency matrix
b)
Incidence matrix
c)
Adjacency list
d)
Edge weight matrix
4.
A multigraph allows:
a)
Self-loops only
b)
Parallel edges between the same pair of nodes
c)
Only weighted edges
d)
Only directed edges
5.
Which tool is primarily for interactive visualization (layouts styling)?
a)
NetworkX
b)
SNAP.py
c)
Gephi
d)
pandas
6.
Best representation for fast adjacency checks (is v a neighbor of u?) on a sparse graph with low memory?
a)
Adjacency list (hash-based neighbor sets)
b)
Edge list
c)
Dense adjacency matrix
d)
CSV table
7.
You need repeated matrix-vector multiplications Ax for algorithms like PageRank on a large graph. Which fits best?
a)
Edge list only
b)
Sparse adjacency matrix (CSR/CSC)
c)
Dense adjacency matrix
d)
Adjacency list
8.
You must count triangles quickly. Which combo is generally most efficient?
a)
Edge list + nested scans
b)
Sorted adjacency lists (set intersections) or sparse matrix ops
c)
Dense matrix + triple loops in Python
d)
CSV join in pandas
9.
You have a tiny dense graph (n <= 2k) and need constant-time adjacency checks. Best structure?
a)
Edge list
b)
Dense adjacency matrix
c)
Adjacency list
d)
Incidence matrix
10.
Which statement is true about file formats?
a)
Edge lists encode whether the graph is directed
b)
Edge lists don't encode directedness; your loader decides
c)
GraphML cannot store attributes
d)
GEXF can't store positions
11.
Which quantity describes the probability that a randomly chosen node has degree k?
a)
Path length
b)
Degree distribution
c)
Clustering coefficient
d)
Diameter
12.
What does a clustering coefficient measure?
a)
Average degree of the graph
b)
Length of the shortest path
c)
Proportion of neighbor pairs that are connected
d)
Probability of edge existence
13.
What is the diameter of a network?
a)
Maximum shortest path distance between any two nodes
b)
Largest connected component
c)
Average degree
d)
Number of triangles in the graph
14.
In an Erdős-Rényi random graph edges:
a)
Are chosen deterministically
b)
Appear independently with probability p
c)
Are weighted
d)
Follow power-law distribution
15.
Which of these is not typically true for real social networks?
a)
High clustering
b)
Heavy-tailed degree distribution
c)
Short average path length
d)
Degree distribution is binomial
16.
The degree distribution of Gn p follows:
a)
Power law
b)
Normal distribution
c)
Uniform distribution
d)
Binomial (approaches Poisson)
17.
What happens in Gn p when average degree k < 1?
a)
Giant component emerges
b)
Graph is fully connected
c)
Components remain small (log n)
d)
Graph becomes bipartite
18.
Which property of real networks is not captured by Erdős-Rényi graphs?
a)
Short paths
b)
High clustering
c)
Existence of giant component
d)
Expansion properties
19.
Watts-Strogatz small-world model achieves:
a)
High clustering + long path length
b)
Low clustering + short path length
c)
High clustering + short path length
d)
Uniform degree distribution
20.
In sampling degree distributions a key pitfall is:
a)
Measuring clustering instead of degree
b)
Sampling biases distort heavy-tail detection
c)
Confusing directed with undirected graphs
d)
Overcounting triangles
21.
Which of the following is a degree-based measure?
a)
PageRank
b)
Closeness Centrality
c)
Degree Centrality
d)
Betweenness Centrality
22.
Betweenness centrality measures...
a)
Number of neighbors a node has
b)
How often a node lies on shortest paths
c)
Eigenvalue of adjacency matrix
d)
Distance to all other nodes
23.
What does PageRank add to eigenvector centrality?
a)
Random teleportation
b)
Larger degree weight
c)
BFS search
d)
Power iteration
24.
Closeness centrality is high when...
a)
A node has many direct edges
b)
A node is close (short paths) to all others
c)
A node is in a spider trap
d)
A node has high out-degree
25.
Which centrality is most useful for finding bridges in a network?
a)
Degree
b)
Betweenness
c)
Eigenvector
d)
HITS
26.
Why might eigenvector centrality assign low score to an important but isolated hub?
a)
It doesn't count paths
b)
It depends on being connected to other central nodes
c)
It ignores out-degree
d)
It uses harmonic mean
27.
Which two problems does PageRank fix compared to plain eigenvector centrality?
a)
Dead ends & spider traps
b)
High clustering & short paths
c)
Duplicate edges & self-loops
d)
Long computation & memory
28.
If teleportation probability = 0 PageRank reduces to...
a)
Degree centrality
b)
Eigenvector centrality
c)
Betweenness centrality
d)
Closeness centrality
29.
Which application best fits betweenness centrality?
a)
Ranking sports players
b)
Identifying bridges in communication networks
c)
Detecting influential websites
d)
Measuring assortativity
30.
In HITS hubs and authorities differ because...
a)
Hubs are in-degree authorities are out-degree
b)
Hubs point to good authorities; authorities are pointed to by hubs
c)
Hubs use teleportation authorities don't
d)
Hubs are based on closeness
31.
What does community mean in a network context?
a)
Group of nodes with equal degree
b)
Group of nodes that are densely connected internally
c)
Group of nodes with no edges between them
d)
Randomly chosen set of nodes
32.
Which measure is often optimized in community detection?
a)
Degree
b)
Modularity
c)
Clustering coefficient
d)
Betweenness
33.
What is the main idea behind spectral clustering?
a)
Use eigenvectors of Laplacian matrix to find partitions
b)
Count triangles in the graph
c)
Rank nodes by centrality
d)
Randomly cut the network
34.
Which of the following methods is hierarchical and greedy?
a)
PageRank
b)
Louvain
c)
Eigenvector centrality
d)
BFS clustering
35.
The Laplacian matrix is defined as:
a)
L = A - D
b)
L = D - A
c)
L = A + D
d)
L = AT * A
36.
Why are modularity-based methods popular?
a)
They are intuitive and scale to large networks
b)
They are guaranteed to find global optimum
c)
They only work on trees
d)
They depend on node labels
37.
What is the Fiedler vector?
a)
The eigenvector with the largest eigenvalue
b)
The normalized degree vector
c)
The eigenvector corresponding to the second smallest eigenvalue
d)
A random initialization vector
38.
What limitation does modularity optimization face?
a)
It cannot detect communities in disconnected graphs
b)
It suffers from resolution limit (small communities missed)
c)
It only works for directed graphs
d)
It requires prior knowledge of k
39.
How does spectral clustering find partitions?
a)
Minimize cut directly
b)
Use degree distribution as threshold
c)
Randomly split eigenvalues
d)
Relax the discrete optimization to continuous then threshold eigenvector values
40.
In motif-based clustering (higher-order spectral) the adjacency is redefined by:
a)
Counting the number of edges between nodes
b)
Counting how often pairs of nodes co-occur in motifs
c)
Counting shortest paths
d)
Using PageRank similarities
41.
Link prediction aims to:
a)
Delete unimportant edges
b)
Predict missing or future edges
c)
Compute shortest paths
d)
Identify communities
42.
In the Common Neighbors heuristic two nodes are more likely to connect if:
a)
They have many mutual neighbors
b)
They are far apart
c)
They belong to different clusters
d)
They have low degree
43.
Jaccard coefficient differs from Common Neighbors by:
a)
Using global paths
b)
Normalizing by total neighbors (Union)
c)
Considering edge weights
d)
Ignoring neighbors
44.
Preferential Attachment favors:
a)
Isolated nodes
b)
Nodes with similar degree
c)
Nodes with high degree
d)
Nodes in separate components
45.
Adamic-Adar gives higher weight to:
a)
Common neighbors with high degree
b)
Rare neighbors with small degree
c)
Randomly chosen neighbors
d)
Nonexistent edges
46.
The Katz index considers:
a)
Only direct neighbors
b)
All possible paths weighted by length
c)
Shortest paths only
d)
Common degree distribution
47.
The Resource Allocation (RA) index can be viewed as:
a)
Each node distributing equal score to all its neighbors
b)
A path counting method
c)
A normalization of degree centrality
d)
Equivalent to PageRank
48.
Structural balance theory implies:
a)
Friend of enemy is friend
b)
Enemy of enemy is friend
c)
Friends are always mutual
d)
Directed trust hierarchy
49.
Which heuristic penalizes high-degree nodes more strongly?
a)
Hub Promoted Index
b)
Hub Depressed Index (or Adamic-Adar context)
c)
Preferential Attachment
d)
Common Neighbor
50.
Why are global methods like Katz computationally expensive?
a)
Require random sampling
b)
Involve matrix inversion over all paths
c)
Depend on node attributes
d)
Only apply to weighted graphs
51.
What does a graph embedding do?
a)
Stores all edges in a list
b)
Represents each node as a low-dimensional vector
c)
Calculates shortest paths
d)
Converts graph to adjacency matrix
52.
DeepWalk and node2vec are inspired by which natural-language technique?
a)
RNNs
b)
word2vec
c)
CNNs
d)
Naïve Bayes
53.
Which idea defines node similarity in random-walk embeddings?
a)
Shared attributes
b)
Co-occurrence in random walks
c)
Number of neighbors
d)
Graph diameter
54.
What key limitation do shallow embeddings have?
a)
They use neural networks
b)
They cannot generalize to unseen nodes (Transductive)
c)
They require node features
d)
They overfit on small graphs
55.
In GCNs node features are updated by:
a)
Random walks
b)
Aggregating and transforming neighbor features
c)
Sorting adjacency matrix
d)
Computing eigenvectors
56.
Which sampling strategy in node2vec allows balancing between homophily and structural equivalence?
a)
Skip-gram
b)
p q biased random walks
c)
Spectral clustering
d)
Negative sampling
57.
Why can GCNs be considered a form of message passing?
a)
Each node sends its embedding directly to all nodes
b)
The adjacency matrix is multiplied once
c)
Nodes iteratively aggregate transformed neighbor features
d)
They use word windows like NLP
58.
What differentiates inductive from transductive graph learning?
a)
Inductive models can infer embeddings for unseen nodes
b)
Transductive models use node features
c)
Inductive models ignore graph edges
d)
Transductive models work across multiple graphs
59.
What is the main drawback of using only adjacency-based similarity in embeddings?
a)
It's too dense
b)
It ignores higher-order connectivity and node roles
c)
It uses too many hyperparameters
d)
It requires node features
60.
Which GNN variant introduces attention mechanisms over neighbors?
a)
node2vec
b)
Graph Attention Network (GAT)
c)
DeepWalk
d)
LINE
61.
Which of the following is not an example of diffusion?
a)
Epidemic infection
b)
Product adoption
c)
Salary increase
d)
Viral video sharing
62.
In the Independent Cascade model each active node...
a)
Has one chance to activate each neighbor
b)
Can activate multiple times
c)
Waits until all neighbors activate
d)
Uses a global threshold
63.
The Linear Threshold model assumes activation occurs when...
a)
A random neighbor activates
b)
Sum of influences >= threshold
c)
Degree > average
d)
Probability > 0.5
64.
Dense clusters usually...
a)
Slow down global diffusion
b)
Accelerate cascades always
c)
Have no effect
d)
Stop local adoption
65.
Influence maximization aims to...
a)
Choose k seeds to maximize spread
b)
Reduce thresholds
c)
Block infection paths
d)
Randomize edges
66.
Submodularity implies that:
a)
Marginal gains diminish as seed set grows
b)
Gains increase exponentially
c)
Function is concave but not monotone
d)
Greedy is exact
67.
Increasing edge probability p in IC model leads to...
a)
Smoother cascade growth
b)
Phase-transition-like jump in spread
c)
Smaller cascades
d)
Uniform activation
68.
The Linear Threshold model best fits...
a)
Rumor spreading
b)
Peer-reinforced adoption
c)
Random failures
d)
Epidemic infection
69.
Embedding-based influence detection relies on:
a)
Node degree alone
b)
Cosine similarity of vectors (latent space)
c)
Centrality ranks only
d)
Threshold sampling
70.
Outbreak detection differs from influence maximization because it...
a)
Selects sensors for early detection
b)
Uses same seeds
c)
Maximizes activation
d)
Ignores timing
100 %
