Homophily and Community Detection

Q1. Jaya is studying a social network of students where each node represents a person and edges
represent friendships. She decides to measure gender-based assortativity by simply computing the
fraction of edges that connect people of the same gender (i.e., intra-gender edges) out of the total
number of edges in the network. She interprets a higher fraction as stronger gender assortativity. What
is wrong with Jaya’s approach? Suggest a more appropriate way to measure gender assortativity and
explain why it’s necessary.
A better approach is to use the assortativity coefficient, known as Newman’s assortativity. This
measures how strongly nodes with the same attribute such as gender are connected while
correcting for chance. It is defined as the Pearson correlation between the attributes of connected
nodes.
Value +1 represents perfect homophily where same-gender connections dominate.
A value of 0 indicates random mixing.
A value of -1 indicates heterophily, or a preference for the opposite gender.
This method is necessary because it provides a normalized and unbiased measure of homophily that
reflects true assortative behaviour rather than effects caused by unequal group sizes.
In summary , Jaya’s method overlooks baseline gender proportions, while using the assortativity
coefficient offers a fair and statistically meaningful measure of gender based homophily.

The answer did not address the specific flaw in Jaya’s method as discussed in lectures.

The question asked why simply taking the fraction of same-gender edges is wrong and what we
should do instead. The expected answer involved:

●​ recognising that group size imbalance biases the fraction,​

●​ subtracting the expected value in a random network, and​

●​ using the probability formula ​we covered in class

Please Use the concepts and method discussed in class, not outside buzzwords. Focus on the baseline
correction idea, not just stating definitions.

Jaya’s approach is incorrect because simply counting the fraction of same-gender edges does not
account for the underlying gender distribution in the network. If one gender is more common, we
would naturally see more same-gender ties even in a completely random graph, so her method can
falsely suggest assortativity.

A better method is to subtract the expected fraction of same-gender edges under random mixing
(while keeping the degree distribution fixed). Since generating many random graphs is impractical,

Refer to the shared notes for more details.

Q2. Both assortativity and modularity compare the observed fraction of edges between node types or
groups with the expected fraction in a random (configuration model) network, and their formulas look
quite similar. If their computation is conceptually similar, what distinguishes assortativity from
modularity in terms of what each measures and how the results are interpreted?
Though Assortativity and modularity are conceptually similar and share similar formulae,
there exist stark differences in what each measures, and how the results are interpreted.
Modularity focuses on measuring the degree to which a network is divided into dense
committees. This essentially tells us how effective the communities formed are by calculating
the difference between itself and a random baseline. On the other hand assortativity tells us
how likely a node is to connect to nodes that are similar to it. This tell us how similar
different nodes from different networks are and gives us a medium to compare them.

The results of both these methods are interpreted very differently - if the degree assortativity
is r =0.3 that means that higher degree nodes tend to connect to other higher degree nodes
but if the value of modularity q = 0.6 this means strong well defined communities exist in the
network. To sum it up modularity focuses more on within communities and between
communities metrics while assortativity focuses on comparison of nodes that are similar to
each other which can be inter community as well given us more low level information
compared to modularity.

You have captured the high-level idea that both modularity and assortativity relate to
patterns in networks, and you've mentioned interpretation with examples: good effort.
However, the explanation became overly complex and missed the key practical distinction we
expected.

In assortativity, the attributes or features (e.g., degree, gender, department) are already
given in the dataset, and you simply measure how much homophily exists based on those
features. You are not discovering groups, you are evaluating similarity among connected
nodes using known labels.

In community detection, only the network is given, no labels or groups are provided. You
must detect communities using an algorithm, and then metrics like modularity check how
good the detected partition is.

Please try to express this in simpler, clearer language. Technical depth is good, but precision
and clarity are more important than making the answer sound complicated.

Q3. Consider a social network consisting of boys and girls.

i) What will be the value of gender assortativity if there are no intra-gender ties (i.e., every edge
connects a boy and a girl)?
ii) What will be the value of gender assortativity if there are no inter-gender ties (i.e., boys connect
only with boys and girls only with girls)?

Q4. Compute the modularity of the given graph, where the two detected communities are highlighted
in purple and blue, respectively.
Fraction of intra gender ties = 6/8

For a random graph, we need to compute 1/(2m*2m) Sum over all pairs (u,v) in same community (du
dv) (Thats what that compex formula means)

= 1/(4*8*8) [2*3 + 2*3 + 3*3]*2 [As the structure is symmetric]

Modularity = 6/8 - 1/(4*8*8) [2*3 + 2*3 + 3*3]*2

Q6. Consider a network of 100 nodes. You assume there can be at most 5 possible communities. A
naïve approach is to assign each node to one of the 5 communities in every possible way, compute the
modularity for each partition, and pick the one with the highest modularity.​
i) How many possible community partitions would this brute-force method need to check?

Given that there is a network of 100 nodes, and that each node can be placed in any of the 5
communities, so for each node there are 5 possibilities to place them.

So for 100 nodes , total possible ways to place them in communities will be 5^100.

This is a very huge number, roughly about 7.9*10^69.

Brute force method has to find the modulairty for 7.9*10^69 partitions. This is not feasible practically.

Nailed it!

Another answer:

f we had 100 nodes and we allowed each node to choose any one of the 5 possible
communities, then the total number of ways to assign them is:

5^100

That is a number around 7.9 × 10⁶⁹ — which is unimaginably large. Even if we consider that
communities are unlabelled (meaning we don’t care which community is called “1” or “2”),
the number of partitions is still around:

∑S FROM 1 TO 5 (100,k) =6.57×1067

So either way, the brute-force approach would have to check an astronomically large
number of possibilities, which is totally impractical.

The answer is right but I am worried about the long dash which is a hallmark of ChatGPT.

ii) What kind of better or more efficient approaches can you think of to detect communities instead?

There are some better algorithms which optimizes to find best modularity: ->Girvan-newmann
algorithm(Divisive): Repeatedly it removes the "most -

->Louvain Method(Agglomerative): It is a fast and effective method that directly tries to optimize
modularity.

The first sentence appears incomplete. Overall, your answer is acceptable, but it would be stronger if
you briefly explained how these methods reduce the complexity of brute-force modularity
maximization. For example, the Louvain method uses a greedy hill-climbing strategy to quickly
improve modularity, while the Girvan–Newman algorithm leverages edge-betweenness to iteratively
remove the most critical edges instead of checking all possibilities.

Another Answer:

Instead of doing brute force, there are better and faster ways to detect
communities. For example:

1)Label propagation:

This is a very quick method where each node keeps updating its label based on
what most of its neighbours have. Over time, labels settle into groups. It’s
extremely fast, but sometimes the results can change depending on the
random initial labels.

2)Infomap:

This method is based on the idea of information flow. It uses random walks in
the network and tries to compress the path taken. Communities are formed in
such a way that random walks stay “inside” a community for longer. This
usually gives very good community structures.

3)Hierarchical clustering:

Here we treat the network like a hierarchy. Either we start by joining similar
nodes step by step (bottom-up) or we start with the whole network and split it
(top-down). We then cut the hierarchy at some level to get our communities.
This is simpler to understand and gives a structured view of how communities
form.

When a question asks for a “better approach,” the expectation is not that you
list sophisticated algorithm names or buzzwords from the internet.

This is an open-ended exam, and I want to see your thinking process, not fancy
terminology.

Before jumping to high-level algorithms like Label Propagation, Infomap, etc.,

first ask yourself:

●​ What is the first tiny improvement over brute-force?​

●​ Can I reduce the search space somehow?​

●​ Can I make a greedy decision instead of checking all cases?​

●​ Can I reuse past computations (dynamic programming idea) instead of

recomputing from scratch?​

The goal is to demonstrate that you can reason from first principles, not just
recall advanced tools.

Think like this:

If I cannot check all partitions, how can I check promising partitions

first?​
How can I speed up calculating modularity step-by-step instead of
recomputing fully each time?

That kind of answer shows understanding and earns marks. Same holds for the
following answer.
Q8. What is configuration model? Explain with the help of a self created example.
Configuration model is a model or a method which is used in a network graph to generate
random networks, when each node has a specified degree. This model connects random
nodes in the graph without changing the degree of each node.

It is used for observing disease spread/information spread in the network when all parameters
are/social activity is same except the connections, which are generated randomly with this
model. (In our course, we have used it in computation of assortativity)
Taking an example of our own group members: Sahithi, Meghana, Srinija, and Abhisha.

If we give a certain number of friends for each person like:

One random generation:

1. Degree for each node

Sahithi = 2
Meghana = 2
Srinija = 1
Abhisha = 1

2. Connecting nodes randomly

Sahithi - Meghana

Sahithi - Srinija

Meghana - Abhisha

All degrees match perfectly.

Second random generation:

1. Connecting them differently with the same degrees

Sahithi = 2

Meghana = 2

Srinija = 1

Abhisha = 1

2. lets connect again,

Sahithi - Meghana

Sahithi - Abhisha
Meghana - Srinija

Degrees match but the nodes are connected differently.

The example is not very clear. A simple figure as we discussed in the class would have done a much
better job. See below:

Given the original graph say as follows

You want a random version of this graph while maintaining the degree distribution.

Create stubs

Connect them randomly

Q9. Consider a social network G(V,E) where each node has a gender label (male/female).​
A student proposes the following pseudocode to measure gender assortativity:
Algorithm GenderAssortativity(G)
1. f_obs ← fraction of edges in G that connect same-gender nodes
2. G_rand ← a random graph generated using the configuration model
(preserving the degree sequence of G)
3. f_rand ← fraction of edges in G_rand that connect same-gender
nodes
4. assortativity_score ← f_obs - f_rand
5. return assortativity_score

(i) What is this algorithm trying to measure?​

(ii) Modify the algorithm so that it correctly estimates the gender assortativity.​
(iii) Conceptually, what aspect of this algorithm makes it an inefficient or incomplete way to measure
assortativity?
A very well done work. Great Job. This is the answer which clearly shows the sincerity and
understanding.

A few tweaks which will make the answer better

1.​ Apart from generating just one random graph, another issue is we are not sure if this graph
was generated with the configuration model (maintaining same degree distribution).
2.​ For part 3, its not just a different answer every time, its computationally very expensive to
generate all possible random graphs and then do an average.
 TEAM BRAINWAVE STORMS

Q10. Apply configuration model to the following network to obtain a random graph.
Q11. You observe a gender assortativity coefficient of r = 0.42 in a friendship network.
Explain what this value means in practical terms.
(i) What does it say about the structure of the network?
(ii) What would r=0 and r=−0.5imply?
R = Fraction of intra gender ties in your network - Fraction of intra gender ties if the network was
random (basline: People are not being friends based on the gender)

R = 0 if both the fractions are equal. This might happen if the network has all males only. Then both
fractions will be 1. There are many other cases also, but R = 0 if there is no inherent gender based
hompophily in the network.

R = -0.5, if fraction of intra gender ties in random network is higher, which means the given network
is heterphilous.

Q12. Write a short pseudocode to compute assortativity based on node attribute similarity without
generating random graphs. Explain the logic behind each step.
Your answer is acceptable overall, but it could be significantly stronger with a few improvements:

1.​ In PageRank problems, the input is generally the adjacency matrix of the network. You
assumed the node degrees are already provided in a separate array, which is typically not the
case, they are computed from the adjacency matrix.​

2.​ In your pseudocode, the final step where assortativity is calculated appears to be inside the
loop. That line should be aligned with the left margin to clearly show it happens after the loop
has completed.​

3.​ The response does not fully reflect a precise and confident understanding of assortativity, as
we discussed in class and as outlined in the handwritten notes.

If you refine these aspects, your answer would be much closer to a perfect response.

Q13. Comment on the range of assortativity coefficient in a graph with proper mathematical
reasoning.
I expected the formulation we discussed in teh class and the answer was simple. Assortativity = F_G -
F_R. Both F_G and F_R are fractions (range 0 to 1). So their difference ranges from -1 to +1.
 Centrality Measures

Q1. Consider an undirected, unweighted network G(V, E) with n nodes. The degree centrality of a
node i is defined as:

C (i) = deg(i) / (n – 1)

where deg(i) is the number of edges incident on node i.

Now suppose the network is weighted, and each edge (i, j) has a weight wᵢⱼ. How would you modify
the above definition to generalize degree centrality for a weighted network?
This qualifies as a perfect answer. Not just explanation, but diagrams and formulae. It shows original
and genuine effort.
Q2. What does the eigenvector of the adjacency matrix of a graph represent?
Give the intuition behind it and explain, in plain English, what its significance is in the context of
networks.

Q3. Fill in the blank: For finding the eigen vector centrality of a network, we need to find the eigen
vector of --------------------------------------. (TRANSPOSE OF ADJ. MATRIX)

Q4. Consider the power iteration method for computing eigenvector centrality. Apply two
iterations of this method on the given network and report the eigenvector centrality values of all
nodes after these iterations.

Inititally every node has value 1.

Then in first iteration

E(1) = 0 (no one points here)
E(2) = E(1) + E(3) = 1+1 = 2
E(3) = E(1) + E(4) = 1+1 = 2
E(4) = E(3) = 1

Then in second iteration

E(1) = 0 (no one points here)
E(2) = E(1) + E(3) = 0 +2 = 2
E(3) = E(1) + E(4) = 0+1 = 1
E(4) = E(3) = 2

Q5. Consider the network shown in the following figure, where the number written inside each node
indicates the number of gold coins it currently possesses. Ignoring effects such as dangling nodes,
evaporation, or damping factors, apply the equal sharing gold coin distribution game and determine
the number of gold coins each node will have in the next iteration.
We can solve this question by assuming that each node ends up having coins that
are shared to it by its neighbours . Every node donates all its coins to its neighbours
and receives coins from its neighbours .
In this situation
Node A has 20 coins and is connected to neighbours B and C
That means A is going to give B and C 10 coins each equally
So at this point A has 0 coins
B and C have 10 coins each
Next when we look at node B
It has 30 coins and is connected to 3 neighbours A ,C and D
So it gives 10 coins each to all the 3 nodes
Now A has 10 coins, C has 20 coins and D has 10 coins
Now when we look at C, it has 60 coins which have to be distributed equally among
its 3 neighbours A,B and D
So all the 3 get 20 coins each
Updated coin tally is
A has 30 , B has 30 and D has 30 coins each
Now the last node that is left is D and has 20 coins which have to be distributed
among B and C as they are its neighbours
Therefore B has 40 coins now
And C has 30 coins
So after all the steps
A has 30 coins
B has 40 coins
C has 30 coins
And D has 30 coins
The original total of coins was 130
And after applying equal sharing gold coin distribution game
We end up still having the 130 coins but now almost equally distributed among the 4
nodes

Q7. Amogh wants to measure the importance of nodes in a directed network using the eigenvector
method. He takes the transpose of the adjacency matrix of the following graph:​
V(G) = {1, 2, 3, 4, 5, 6} and E(G) = {(1,2), (1,3), (3,2), (3,4), (1,5), (5,6), (6,5)},​
and computes its eigenvector to determine node importance.

(i) Explain the intuition behind using eigenvectors of the adjacency matrix to measure node
importance.
The above answer is not sufficient as it does not mention how the transpose of the matrix and its eigen
vector capture this idea. Yes the eigen vector for each node depends on the scores of the nodes
pointing to it but how, how is the computation done? ​
(ii) Identify two major flaws in Amogh’s approach and describe how you would correct or improve
it.

The explanation is correct but unfortunately it doesn’t quite depict the same level of understanding as
we discussed in the class. Instead of using complex structures like strongly connected component, you
could have simple stated that nodes 2 and 4 created leakage in the system and rest of the coins are
equally distributed between nodes 5 and 6, so even the pagerank values for them will also not be
meaningful.
High outdegree or indegree? Also, what is the issue if you do not have edge weights? I don’t see this
as problem. The question was simple, there are 2 issues with pagerank, one is the leakage that can be
created by the dangling pointers and the second is the spidertrap problem: A bunch of nodes linking
only between them and eating up all the gold.

Q8. In your own words, explain how the coin distribution game used for computing PageRank is
conceptually equivalent to the random surfer model. Discuss the intuition behind the equivalence
and describe how the model handles corner cases such as dead ends and disconnected nodes.

The PageRank formula captures the same idea behind both the coin (or gold) distribution game and
the random surfer model.

In the coin distribution game, each node starts with some gold and distributes it equally among the
nodes it points to. The term ∑PR(v)/N(v) in the formula represents this process, each node v that
points to u gives an equal share of its gold (1 divided by its outdegree) to u. Over several rounds, the
system reaches a steady state where the amount of gold each node has represents its importance in the
network.

In the random surfer model, the same logic applies in probabilistic terms. The “gold” becomes the
probability of the surfer being on a particular page. For the surfer to be at node u in the next step, they
must currently be at one of the nodes pointing to u, and the probability of moving from that node to
uuu is again 1 divided by its outdegree. Thus, both models capture how importance (or probability)
flows through outgoing links in a network.

To handle corner cases:

●​ Dead ends: In the coin game, a node with no outgoing links redistributes its gold equally
among all nodes, preventing loss of total gold. In the random surfer model, if the surfer
reaches a dead end, they “teleport” to any other page in the network, ensuring the process
continues.​

●​ Spider traps: To avoid all the gold (or probability) getting stuck within a small group of
interlinked nodes, we introduce a damping factor (typically 0.8 or 0.85). This means only
80% of the gold is redistributed through normal links, and the remaining 20% is spread
equally among all nodes. In the random surfer model, this corresponds to the surfer
continuing to follow links with 80% probability and randomly jumping to any page with 20%
probability.
 Link Prediction

Q1. Shreya is working on a link-prediction task for a social network. She takes all possible pairs of
users, labels existing connections as positive examples and non-connected pairs as negative examples,
and then randomly splits them into training and test sets. Her model shows very high accuracy,
precision, and recall.

But her friend argues that her evaluation is misleading and her ML approach has a fundamental flaw
related to real-world networks.

What is the issue with Shreya’s approach, and why do ML models often fail in this situation?

Q3. In link prediction, the common-neighbors method counts how many mutual neighbors two nodes
share. Explain why using only the raw count of common neighbors may not always be sufficient for
accurate link prediction. Give a graph example illustrating a situation where two different node pairs
have the same number of common neighbors, but intuitively one pair should have a stronger
likelihood of forming a link than the other.

Q4. A recruiter is comparing résumés of two candidates. Both candidates list:

●​ Microsoft Word / Excel: very common skills​

●​ "Rust programming for embedded cryptography systems": a rare and specialized skill​

Answer the following:

(a) Which shared skill gives a stronger indication that the two candidates work in very similar
technical domains? Explain your reasoning in natural terms (without using graphs/matrices).

(b) Which link prediction techniques relate to this idea? Explain with an example.

Q5. Random walks are used in PageRank as well as in link-prediction methods. Explain, in plain
English, how the behavior of random walks differs in these two settings, especially in terms of where
restarts happen and why they happen. Also comment on the idea of local random walks used in link
prediction. How is their restart logic different from PageRank, and what goal does that serve?
No formulas needed; focus on the intuition.

Q6. Apply any 2 local link prediction methods for nodes 2 and 4.
Q7. A new student joins a university social platform. They have not connected with anyone yet and
have no profile history or interactions. Explain why standard link prediction techniques struggle in
this situation. What strategies could be used to handle such cases? Provide examples inspired by real
online systems (e.g., LinkedIn, Instagram, academic networks).

Q8. Networks often grow through triadic closure “a friend of my friend is likely to become my
friend.”But sometimes the most valuable new links happen across structural holes, connecting
completely different communities. Explain both ideas with a real-world analogy and discuss why
relying only on triadic closure can miss important links. Mention one situation where predicting a
cross-community link is more useful.

Triadic closures are clusters with 3 nodes having connections with one another.
- Let there be a group of 3 people, where 2 of them are friends. It implies that it is very
likely that the third one turns out to be a friend or will become a friend (given that the
third person is a friend of either).
Structural holes are gaps between two individuals or two clusters with one common node
connecting them (broker node) such that the nodes of a certain cluster are unaware about the
information about the nodes of the other cluster apart from the broker node..
- Islands. People on islands are closer knit than a major city, form a closer and more
robust bond, sharing similar information.
The major city is one cluster, the island is one cluster. They are connected to share
information with building roads, let's say. Major cities have more information
regarding the technical aspects and innovations regarding the building of roads. The
islands, on the other hand, have information and experience on how to build roads
near water bodies and avoid cracking of the tarmac due to pressure from the water
body/earth.
- People from the major cities don't know how to build roads properly near water
bodies, while the island people are a bit technologically behind. Here the island will
benefit with new information regarding building roads in a more feasible and efficient
way using technology. The cities will benefit with more traditional approaches to
build roads near water bodies to prevent tarmac damage due to water and moisture.
Only relying on the information that is present in a triadic closure or cluster can be harmful
since there isn't an inflow of new information. Only the previous information going around in
the cluster is used by the nodes

Q9. Suppose you are predicting collaborations between researchers. You have two categories of
information:

●​ Network structure (co-authors, mutual collaborators, citations)​

●​ External attributes (research topics, conference attendance, institute)​

Explain when only graph structure may fail, and when combining structure with content/attributes
is necessary. Give an example showing how each type of information can change the prediction.
The Social Computing Project example that you mentioned in the end captures the essence of the
problem. However, the initial part of the answer focuses more on the cold start problem and missing
data. A more specific answer is appreciated. Could you provide an example graph with some links and
attributes where edge based link prediction gives you a different answer and attributes based link
prediction different. That was the crux of the question which remains unaddressed.

An example may be,

Assume you are Riya, a CS student in Social Computing class. Cherry, Dan and Bimla are also in
your Social Computing class from CS. Even though you don’t them, a link prediction algorithm might
suggest you will become friends because of these shared attributes. This is attribute based link
prediction. On the other hand, assume you are friends with AI students Pete and Chris Neha from
another elective and your friendship is strong, then you will be friends with Neha soon (Triadic
closure), that is edge based link prediction.
Remember, a picture is equal to 1000 words.

Another Answer:
Q10. In real life, links are not always meaningful. For example:

●​ A person accepts a random LinkedIn request​

●​ Two researchers appear as co-authors due to a large consortium paper​

●​ An Instagram follow happens because of a promotion or bot network​

Explain why blindly trusting observed links can reduce link-prediction quality. Suggest one strategy to
handle such noisy links.

Real world links arent always meaningful. A linkedin accept, a promotional/bot/courteous

instagram follow or co-authoring a big group paper might not mean that people actually
have/want to connect deeply. So if we treat these weak or accidental links as strong ones
the resultant network might not represent the reality. So if we are to predict whether two
nodes are to be connected in the future based on links that might be inclined towards
arbitrariness as opposed to actual meaning then the link prediction quality reduces
drastically.

Naive strategy:
Set some probability which defines the likelihood of an edge getting cut.
this would run through the whole graph such that if person 'A' has the habit of following
people regardless of closeness and another person 'B' who only follows those whom he
considers himself close to, then we set the probability of cutting an edge of person A higher
than that of person B. But the limitations of this method include not being able to
differentiate between peoples habits and inclinations, and the chance of cutting actually
meaningful connections.

The way to differentiate between person A and B could be :

1.​ Assume a situation where Sanket follows Madhav, then if sanket follows a lot of
madhav's followers (lets name these followers- martians) then that could imply that
sanket represents person A's behaviours.
2.​ Set an initial limit (some computed value). Depending on the number of 'martians'
sanket follows, compute a curve that accurately defines the probability value.
Its a well written answer, would have liked some more clarity on the last line in point 2 above.

Another answer: