Carlos Trindade's Graph Algorithms Quiz Blog

 In the context of community detection, the generalized modularity \(M\) of a network with \(L\) links and \(n_c\) communities is given by: \[ M = \sum_{c=1}^{n_c}{\left[ \frac{L_c}{L} - \left( \frac{k_c}{2L} \right)^2 \right]}\] where \(L_c\) is the total number of links within the community \(C_c\) and \(k_c\) is the total degree of the nodes in this community. Considering the following statements: I. Modularity has a resolution limit, as it can't detect communities smaller than a factor proportional to \(\sqrt{2L}\). II. A community \(C_c\) contributes positively to \(M\) only if the fraction of internal links \(\frac{L_c}{L}\) exceeds the expected fraction \(\left(\frac{k_c}{2L}\right)^2\) under a null model that preserves the degree sequence. III. The modularity \(M\) is bounded in the interval \([0,1]\), where \(M = 1\) corresponds to a perfectly modular network. IV. The partition with the maximum modularity \(M\) offers an optimal community structure. It is correct  to ...

Epidemiologists are studying the spreading of a disease through an interaction network. After collecting data, they find that the network's degree distribution follows a power law \(p_k \sim k^{-\gamma}\) with exponent \(\gamma = 2.5\), suggesting that a small number of highly connected individuals ("superspreaders") play a dominant role in transmission. The network has a minimum degree of \(k_{\text{min}} = 2\), meaning every user follows at least two others, and an average degree of \(\langle k \rangle = 8\). Structural analysis reveals a cutoff \(k_s = 64\), beyond which the simple-graph constraint begins to limit how hubs can connect to one another. Based on this information, which of the following alternatives is correct? A) \(k_{\text{max}} = 120\), and the network presents structural assortativity because \(k_{s} < k_{\text{max}}\). B) \(k_{\text{max}} = 64\), and the network does not present structural disassortativity because \(\gamma > 2\). C) \(k_{\text{m...