ICUnicamp.blogspot.com

Consider the problem of the propagation of an SIS infection in two types of networks: An aggregated network , constructed by summing all contacts over the course of a week. A temporal network , in which each contact occurs only at the moment when it was recorded. The figure below shows the fraction of infected individuals I(t) over time in each network. The structural and epidemiological parameters are: Aggregated network : average degree \( \langle k \rangle = 12 \) second moment \( \langle k^2 \rangle = 260 \) Temporal network : effective average degree \( \langle k_{\text{eff}} \rangle = 5 \) effective second moment \( \langle k_{\text{eff}}^2 \rangle = 40 \) Model rates: transmission \( \beta = 0.04 \) recovery \( \mu = 0.02 \) Consider the approximate epidemic threshold for general networks: \[ \lambda_c = \frac{\mu}{\beta}\,\frac{\langle k\rangle}...

Consider the network below, where each edge is labeled with its edge betweenness centrality .   After applying a divisive community detection algorithm based on edge betweenness, the first split of the network yields the two communities shown below: Using only this two-community partition, what is the modularity of this division? Round your answer to two decimal places . 0.16 0.20 0.24 0.28 None of the above Original idea by: Luiza Barguil Inspired by: Arasteh, A., & Alizadeh, M. (2018). A fast divisive community detection algorithm based on edge degree betweenness centrality. Labels: Communities

Questão 5 — When 1.5 Beats 2: The Strength of Christofides under the Triangle Inequality Consider a symmetric, weighted, complete graph \( G = (V, E) \) with \( |V| = 6 \) vertices that satisfies the triangle inequality. The minimum spanning tree (MST) of \( G \) has total cost \( c(T) = 60 \). Two algorithms are applied to this graph: Rosenkrantz–Stearns–Lewis (RSL) Finds \( T=\mathrm{mst}(G) \); doubles each edge of \(T\) to get an Eulerian multigraph \(T'\); finds an Euler tour and removes repeated vertices. Performance guarantee: \( c(C_{\mathrm{RSL}}) \le 2\,c(TSP^*) \). Christofides Finds \( T=\mathrm{mst}(G) \); lets \( S \) be the set of odd-degree vertices of \(T\); finds a minimum perfect matching \( M \) on \(S\); adds \(M\) to \(T\) to get an Eulerian multigraph \(T'\); finds an Euler tour and removes repeated vertices. Performance guarantee: \( c(C_{\mathrm{Chr}}) \le 1.5\,c(TSP^*) \). Answer in one go: (i) the maximum tot...

Em teoria dos grafos, o algoritmo do Caixeiro Viajante (TSP) é um clássico: dado um conjunto de cidades e as distâncias entre elas, o desafio é encontrar o caminho mais curto que visita cada cidade exatamente uma vez e retorna ao ponto de partida. Mas, além de seu fascínio matemático, o TSP é uma metáfora poderosa para problemas reais de decisão, inclusive em política. Enquanto estudava o algoritmo, percebi o quanto ele se conecta ao meu projeto de rede de Emendas Parlamentares . Cada deputado pode ser visto como um “viajante” que precisa distribuir suas emendas (recursos) entre diversos municípios, tentando equilibrar  alinhamento político e retorno eleitoral . Na prática, isso cria um problema de otimização multidimensional: como percorrer os “nós” (municípios) maximizando o impacto político com o menor custo possível? Modelar esse comportamento em grafos permite testar hipóteses como: Deputados priorizam municípios geograficamente próximos? Há padrões regionais que...

When Identical Degree Distributions Hide Distinct Correlation Patterns “Two networks may share the same degree distribution and yet encode profoundly different organizational principles.”   Context Consider two undirected networks, A and B , each with the same degree distribution $P(k)$ and identical average degree $\langle k \rangle = 6.2$. Despite this structural similarity, empirical analysis shows that the average neighbor degree function $k_{nn}(k)$ behaves differently for each network: For Network A , $k_{nn}(k)$ increases approximately as a power law $k_{nn}(k) \sim a,k^{\mu}$ with $\mu > 0$. For Network B , $k_{nn}(k)$ decreases with $k$, following $k_{nn}(k) \sim a,k^{\mu}$ with $\mu < 0$. Definition The Pearson correlation coefficient of degree correlation r r r is defined as: r = ∑ j , k j k   ( e j k − q j q k ) σ 2 r = \frac{\sum_{j,k} j k \,\big(e_{jk} - q_j q_k\big)}{\sigma^2} r = σ 2 ∑ j , k ​ jk ( e jk ​ − q j ​ q k ​ ) ​ where: ejk e_{jk} e ...

Entendendo a Correlação de Grau em Redes: quem se conecta com quem? Você já parou para pensar se os “nós populares” de uma rede tendem a se conectar entre si — ou se preferem fazer amizade com nós menores, menos conectados? Essa simples pergunta leva a um dos conceitos mais elegantes da Ciência de Redes : a correlação de grau  e o coeficiente de assortatividade . O que é o grau de um nó? O grau  de um nó é o número de conexões que ele possui. Em redes não direcionadas , é apenas o número de vizinhos. Já em redes direcionadas , distinguimos: grau de entrada (in-degree) : quantas conexões chegam; grau de saída (out-degree) : quantas conexões saem. Esse número simples — o grau — é a base de muitas propriedades emergentes das redes complexas. Correlação de grau: quando a afinidade cria estrutura A correlação de grau  mede o quanto o grau de um nó influencia o grau dos nós com que ele se conecta. Em termos simples: quem se conecta com quem: Quando nós de alto grau se conectam ...

Hoje mergulhei em um dos temas mais fascinantes da Teoria dos Grafos: fluxo em redes . Mais do que uma abstração matemática, esse conceito aparece em situações muito concretas — da logística de caminhões até a coordenação militar da OTAN O que é uma Rede de Fluxo? Podemos imaginar uma rede de fluxo como um sistema de canos de água ou de caminhões em estradas : Existe uma fonte (source) que gera o recurso. Um sorvedouro (sink) onde esse recurso precisa chegar. E arestas com capacidades que limitam quanto pode ser transportado por cada conexão. Três propriedades fundamentais governam esse sistema: Conservação : tudo o que entra em um nó intermediário precisa sair (não há estoque local). Antissimetria : o fluxo de ida e volta se cancelam (se A envia 4 para B, então B envia –4 para A). Valor do fluxo : corresponde ao total que sai da fonte (ou entra no sorvedouro). Rede Residual: onde a mágica acontece Quando já usei parte de uma estrada, sempre sobra a possibi...