Blog de Grafos do Daniel

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 cho...

The Euclidean Traveling Salesman Problem (Euclidean TSP) is a special case of the symmetric TSP where each city corresponds to a point in $\mathbb{R}^d$ and the cost $c_{ij}$ of traveling between cities $i$ and $j$  equals the Euclidean distance between their coordinates. As the Euclidean distance is symmetric and satisfies the triangle inequality, Euclidean TSP is a special case of Metric TSP, allowing approximation algorithms to be used for a solution. Consider the Euclidean TSP on 5 cities, located at A(0, 0) B(2, 0) C(2, 1) D(0, 1) E(1, 1) Which of the following statements is true ? a) The optimal tour is achieved by ABCED, costing approximately 5. b) Any Euclidean TSP can be solved in Polynomial time using the ILP formulation. c) The Nearest Neighbor heuristic starting from any node always yields a tour of cost 6. d) The Cheapest Insertion heuristic is better than the Nearest Neighbor for any starting single-node cycle.  e) None of above Original Idea: Daniel Gardin

Consider a growing network constructed according to the Barabási-Albert (BA) model with the following parameters: Linear preferential attachment: each new node connects to existing nodes with probability proportional to their current degree. We start with a single node, and each new node adds a single edge ($m=1$), generating a tree. The network is sufficiently large ($t \to \infty$), so that the asymptotic degree distribution is well-defined. Under these conditions, what is the expected value of the degree distribution exponent $\gamma$, defined by $P(k) \sim k^{-\gamma}$? a) $\gamma \leq 1$ b)  $\gamma = 2$ c)  $\gamma = 3$ d) There is not enough information to estimate $\gamma$ e)  None of the above Original idea: Daniel Gardin

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

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...

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^...