Blog de Grafos do Daniel

Unicamp has been plagued by a persistent, annual outbreak of a highly contagious but rarely fatal disease called  Network-pox . Network-pox is an SIS-like pathogen (Susceptible-Infected-Susceptible) in which recovery from symptoms (a dangerous aversion to studying network science) confers only temporary immunity, so students quickly become susceptible again. The typical university population forms a highly heterogeneous contact network, where some students attend every lecture, participate in multiple clubs, forming large hubs, but others occasionally attend classes, study in their rooms, and have limited social interaction. Thankfully, Prof. Meidanis has found a cure for the Network-pox, the MO412 Vaccine, leading to a mass vaccination program, successfully immunizing 92% of the students at Unicamp at random. However, the question of whether the disease has been eradicated remains unsolved. A previous study has revealed that the Unicamp network was scale-free, with...

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