Algoritmos em Grafos - Alexandre

 You are a systems analyst at a major data center, and you are tasked with evaluating the robustness of your facility's connection to the wider Internet infrastructure against random node failures. Your analysis of the network topology reveals that the average degree <k> of the nodes is 6.25. Based on your understanding of robustness, what breakdown threshold does the network at the datacenter need to have to display enhanced robustness? a) 0.16 b) 0.17 c) 0.84 d) 0.85 e) None of the above Original idea by: Alexandre Petrachini 

Classify the alternatives as true or false, regarding degree correlation properties in networks: I: For assortative networks, the transition to a giant component takes longer, as hubs preferentially connect to each other. II: For a disassortative network, the degree correlation function knn (k) increases with k. III: Structural disassortativity is a phenomenon observed in scale-free networks where  γ < 3 , which arises because the network lacks a sufficient number of links to connect the large hubs in a neutral way. IV: Assortative networks have a shorter average path length than neutral networks, but also a larger network diameter. A) T-F-T-T B) T-F-F-F C) F-F-T-T D) T-F-F-T E) None of the above Original idea by: Alexandre Petrachini

 A friend of yours has published a pioneering research paper in a niche area, and it has gathered several citations from other researchers. The directed graph below shows the citation relationships among papers in this area. Your friend is extremely happy with the results, given that his Paper A is already the most influent paper in the network, with an incoming degree of 4. Curious, with your knowledge on network science, you want to understand what the probability of a new paper is citing paper A.  You are happy with rough approximations, so you frame this problem using a copying model of a directed network. With the probability of linking uniformly at random to an existing paper of p = 0.4, and the probability of copying of a link from a random citation of 1 - p, what is the probability of a new paper connecting to paper A? Round to two decimal places. a) 0.1 b) 0.20 c) 0.29 d) 0.21 e) None of the above Original idea by: Alexandre Petrachini

 In a social platform, you can be friends with people from many different countries. Suppose you pick two random people with entirely different profiles, what can you expect from the number of steps (friend-of-a-friend connections) that would take for these two to connect? Assume the social platform follows a scale-free network. a) There isn't a feasible number of steps connecting two people, since most people in the network are isolated. b) It could take hundreds of steps, since there isn't anyone in the network that knows a lot of people. c) It will take a small number of steps, as eventually someone will know a lot of people. d) It will take an equal number of steps, as everyone knows the same amount of people. e) None of the above. Original idea by: Alexandre Petrachini

A fungal colony, whose hyphae form a network called the mycelium, started growing on a piece of bread left unattended. The colony started small, at an initial number of spores N = 5000 . It is known for this species to create hyphae (links) at a probability that depends on time, described by the function below: Where t is time in days. Assume that the number of spores remains constant over time and that it follows an Erdős-Rényi network . Give n two different intervals: A day has passed Three days have passed Assign the correct alternatives in respect to attributes about the mycelium growth. a) As one day passes, the network is subcritical, and by three days, it’s supercritical. b) As one day passes, the network is subcritical, and by three days, it remains subcritical. c) As one day passes, the network is critical, and by three days, it’s supercritical. d) As one day passes, the network is already supercritical. e) None of the above Original idea by: Alexandre Petrachini

  A group of friends like to relay gossip through messages, the graph below shows how messages usually flow between them. Lucas noticed that messages sent by him were being distorted, and wanted to understand more about their network and who can impact the messages he sends. Consider the following sentences and mark them as true (T) or false (F): Pedro and João have, respectively, a clustering coefficient of 1/3 and 1/6. The average degree in this network is 16/6. The maximum path length in this network is less than 4. Pedro has the highest clustering coefficient. Ana and Davi have the smallest clustering coefficient. The correct option that matches the sentences is: T-T-T-T-F F-T-T-F-T F-T-T-T-F T-F-T-T-F None of the above Original Idea by: Alexandre Petrachini