Data mining MCQ 2

In graph mining, a graph is best defined as:

A set of nodes connected by edges

What does the degree of a node represent?

The number of edges connected to the node

In an Erdős–Rényi random graph, what does the parameter p represent?

The probability that an edge exists between two nodes

What typically happens when n · p ≈ 1 in an Erdős–Rényi graph?

A giant connected component starts to emerge

Why is the largest connected component often studied in random graphs?

It reveals connectivity and phase transition properties

What information does a degree distribution provide?

How node degrees are distributed across the graph

Which characteristic is typical of an LFR benchmark graph?

Power-law degree distribution with known communities

Why are LFR graphs commonly used in community detection studies?

They provide ground-truth communities

What is a community in a graph?

A set of nodes densely connected internally and sparsely connected externally

What is the main principle behind the Louvain community detection algorithm?

Maximizing modularity

Why might the Louvain algorithm fail to recover the ground-truth communities of an LFR graph?

Maximizing modularity does not always match true communities

What does Normalized Mutual Information (NMI) measure?

Similarity between two partitions of nodes

What is the key idea of the Girvan–Newman algorithm?

Removing edges with high betweenness

Compared to Louvain, the Girvan–Newman algorithm is often:

More computationally expensive but sometimes more accurate

What is the goal of graph (node) embeddings such as Node2Vec?

To convert nodes into low-dimensional vector representations

What is an Erdős–Rényi random graph?

A graph where each pair of nodes is connected with probability p

What is an LFR graph mainly used for?

Benchmarking community detection algorithms

What is community detection?

Finding groups of densely connected nodes

What is the Louvain algorithm based on?

Modularity maximization

What is the core principle of the Girvan–Newman algorithm?

Removing edges with high betweenness

What does normalized Mutual Information (NMI) measure?

Similarity between two community partitions

What is the goal of node embeddings?

To map nodes into low-dimensional vector spaces

LFR graph

They have a priori known communities and are used to compare different community detection methods

Which statement best compares Louvain and Girvan–Newman?

Louvain maximizes modularity, Girvan–Newman removes high-betweenness edges

Why can Girvan–Newman outperform Louvain on LFR graphs?

explicitly separates communities via edge removal

What is a key difference between LFR and Erdős–Rényi graphs?

LFR graphs have realistic degree distributions and known communities

What is the main difference between Node embeddings and Community detection ?

Community detection finds groups; embeddings create vector representations

Why is NMI preferred over raw accuracy for community detection?

Labels are arbitrary and permutation-invariant

Acceed the ground-truth communities of the graph with nx.get node attributes(lfr,’community’)

The returned ground-truth is a dictionnary, which keys correspond to nodes, and values corre spond to a set of nodes forming a community. The communities are disjoint, meaning that each node is contained in one single community

Divisive clustering on Edge-Betweenness

• You start with the entire network as a single cluster.

• Then, you recursively split it into smaller communities until meaningful groups emerge

Why are Erdős–Rényi graphs often considered unrealistic models of social networks?

They assume uniform edge probability between all node pairs

LFR graph degree distribution ?

heavy-tailed (power-law-like) distribution

Why is the Karate Club graph commonly used in graph mining?

It has a well-known real community split

Why can the Louvain algorithm fail to recover the true communities in an LFR graph?

Modularity maximization may not align with planted communities

Which statement about scalability is correct?

Louvain is generally more scalable than Girvan–Newman

What is the main conceptual difference between edge betweenness and modularity?

Edge betweenness identifies bridges; modularity evaluates partition quality

How does community detection differ from finding connected components?

Communities allow sparse connections between groups

Why is Normalized Mutual Information (NMI) preferred over accuracy for evaluating communities?

Community labels are arbitrary and unordered

How do node-embedding-based methods differ from classical community detection?

They transform nodes into vectors before clustering

Which comparison is correct?

Degree counts neighbors, betweenness counts shortest-path participation