Agglomerative Clustering Communities

An important enterprise, after detecting a major overlap of work and subsequent redundant effort, has begun analyzing intra-organizational collaboration to impose a more coherent structure across its teams. You, as an avid network scientist, have decided to collect data from ten teams, labeled A through J, forming an undirected link between any pair of teams that share at least one substantive project dependency, documented code module, or operational handoff.

With the built graph, you could then find which teams have the most in common, modeling possible cooperations as communities within this graph. After testing the main agglomerative clustering algorithms, you have decided on the following partition, leading to the communities {A, B, C, D, E, G} and {F, I, J, H}, obtained by analysing the resulting dendogram.

The chosen similarity scores between teams u and v were simply 1 if there was a link between them, and 0 otherwise.



The correct analysis of this selection would be

a) By choosing 0/1 similarity and the average linkage, stable communities could have been formed. This is evidenced by the strong communities produced when the distance is cut to 2.0.

b) The chosen cut is the only one from the set of all possible partitions induced by cuts in the dendrogram that produces strong communities.

c) The clustering algorithm that produced this dendrogram cannot have used a complete linkage, as I and J would have always been in different communities.

d) An agglomerative clustering with 0/1 similarity and single linkage could never produce this dendrogram.

e) None of the above


Original idea by: Daniel Gardin

Comments

Post a Comment

Popular posts from this blog

Sierpiński Gasket Graphs

Image
The Sierpiński gasket graphs form one of the most studied examples of self-similar structures in graph theory [1]. They provide a discrete analogue of the classical Sierpiński triangle fractal, preserving both its recursive construction and its combinatorial richness. The sequence begins with the complete graph on three vertices, $S_{1}$, and at each subsequent step, $S_{n+1}$ is obtained from $S_{n}$ by subdividing every triangular face. New vertices are placed at the midpoints of its edges, and these are joined to form a smaller triangle inside. Repeating this process yields a hierarchy of graphs whose geometry captures the recursive pattern of the underlying fractal.   Figure 1. The first 4  Sierpiński gasket graphs. Taken from  Bunimovich et. al (2016) [2] Given this sequence, what is the Global Clustering coefficient of $S_n$, for $n\geq2$ and its limit when $n \to \infty$? $$\textbf{a)}\quad \frac{3^n}{3^{n}-2}, \quad 1$$ $$\textbf{b)}\quad \frac{4\cdot 3^...
Read more

Random Isolated Vertex

Consider a graph consisting of $n$ vertices in which each possible edge is included with probability $p = p(n)$ (a probability that explicitly depends on the size of the graph). This construction provides a probabilistic framework, as described by Gilbert [1], to study typical properties of graphs as $n$ increases. Denote this graph by $G(n, p)$, and consider $p(n) = \frac{1}{\sqrt{n}}$. What is the probability of finding an isolated vertex ( i.e.,  a vertex with no neighbours) in $G(n, p)$ as $n$ increases? Hint: Consider that the probability of finding an isolated vertex in a random graph with $n$ vertices is $P_\mathrm{isolated}(n) = (1-p)^{n-1}$. a) It increases with $n$, approaching $P_\mathrm{isolated}(n) = 1 - \frac{1}{n}$, converging to 1. b)  It increases with $n$, approaching $P_\mathrm{isolated}(n) = 1 - \frac{1}{\sqrt{n}}$, converging to 1. c) It decreases with $n$, approaching $P_\mathrm{isolated}(n) = \frac{\log n}{n}$, converging to 0. d)  It decr...
Read more

Scale-free Networks

The scale-free regime of a network is defined for graphs whose degree distribution is $p(k) \propto k^{-\gamma}$ for $\gamma \in (2, 3)$. Which of the following properties about the resulting networks is true as $\gamma$ approaches $2$ from the right? a) They become indistinguishable from an Erdős–Rényi random network, because their second moment, $\langle k^2 \rangle$, decreases. b)  Vertices with extremely large degrees become more common. c) The expected distance between nodes only increases. d) The tail of $p(k)$ becomes heavy-tailed, indicating a decrease in the average degree, $\langle k \rangle$. e)  None of the above Original idea: Daniel Gardin
Read more