Practice Exercise 04_ Tópicos em Computação I - G1_T1 - 2023_2

Prévia do material em texto

(1525101) Tópicos em Computação I Ques�onários Prac�ce Exercise #04
Prac�ce Exercise #04
Entrega 26 nov em 23:59 Pontos 5 Perguntas 4 Disponível até 26 nov em 23:59
Limite de tempo Nenhum
Este teste foi travado 26 nov em 23:59.
Histórico de tenta�vas
Tenta�va Tempo Pontuação
MAIS RECENTE Tenta�va 1 27 minutos 5 de 5
 As respostas corretas estão ocultas.
Pontuação deste teste: 5 de 5
Enviado 16 nov em 12:13
Esta tenta�va levou 27 minutos.
2 / 2 ptsPergunta 1
Sua Resposta:
Suppose that we consider the full popula�on of the world, and suppose that from each person in the world,
we create a directed edge only to their ten closest friends (but not to anyone else they know on a first-name
basis). In the resul�ng “closest-friend” version of the social network, is it possible that for each pair of people
in the world, there is a path of at most six edges connec�ng this pair of people? Explain. 
Based on the content provided in the documents, the answer to the original ques�on can be influenced by
various findings and theore�cal models concerning social networks and small-world phenomena. For instance,
within the context of Facebook, it has been observed that 99.6% of all pairs of users are connected by paths of
5 degrees (6 hops), and 92% are connected by just four degrees (5 hops) . This suggests that in a highly
interconnected digital social network like Facebook, the majority of user pairs are within six degrees of
separa�on.
Other studies have found similar results with average path lengths ranging from 5 to 7 hops . This
demonstrates that even in broader and more diverse networks, the six degrees of separa�on theory can be
generally valid.
However, it is crucial to note that small-world graphs have a very short diameter and a high clustering
coefficient, unlike random graphs which have a short diameter but a very low clustering coefficient . This
implies that real friendship networks tend to have many densely interconnected local �es (high clustering) but
s�ll allow for "shortcuts" that connect different friend groups, enabling the short distance between any two
individuals.
The Wa�s-Strogatz model, for example, starts with a ring of n ver�ces connected to their k nearest neighbors
by undirected edges, and then, with a certain probability p, reconnects these edges to a vertex chosen
randomly across the en�re ring, repea�ng the process un�l one lap is completed . This model is a means to
understand how small-world networks might arise and supports the idea that there is a short distance
between any two points in a network, even with directed connec�ons to a limited number of close friends, as
in your ques�on.
Therefore, although the original ques�on may not have a defini�ve answer without further data, exis�ng
models and observa�ons suggest that it is possible that, even in a directed network where each person is
connected only to their ten closest friends, there could s�ll be a path of at most six edges connec�ng any pair
of individuals, at least in theory and under certain ideal connec�vity condi�ons.
1. It has been observed that within the context of Facebook, "99.6% of all pairs of users are connected by
paths with 5 degrees (6 hops)" and "92% are connected by only four degrees (5 hops)" .
2. Other studies indicate that, generally, "a great part doesn’t reach the des�na�on" and the "average path [is]
5 to 7 hops" .
3. The characteris�cs of small-world networks are described as having "very short diameter and high
clustering coefficient," unlike random graphs which have "short diameter but very low clustering
coefficient" .
4. The Wa�s-Strogatz model for small-world networks is outlined as beginning with "a ring of n ver�ces
connected to its k nearest neighbors by undirected edges," and then poten�ally reconnec�ng edges with a
certain probability to create a small-world network
1 / 1 ptsPergunta 2
Sua Resposta:
Considering the small-world phenomenon and its proper�es (short distances and high clustering coefficient),
try to describe a network and its node's behavior that can produce this phenomenon. For instance, in vehicular
networks, vehicles such as cabs and buses can contribute to crea�ng shortcuts in the graph, reducing the node
distance. 
The small-world phenomenon is characterized by networks where most nodes can be reached from every
other by a small number of steps, despite the network's large size. This is o�en due to the presence of a few
key nodes that act as shortcuts, connec�ng otherwise distant parts of the network. To describe a network that
exhibits the small-world phenomenon, let's consider the following a�ributes and behaviors of nodes:
High Clustering Coefficient:Most nodes have a high degree of local interconnec�vity, meaning they are part of
�ghtly-knit clusters or groups. These clusters could represent social circles, geographical communi�es, or areas
of common interest in social networks.
Short Average Path Lengths (Shortcuts): Within the network, some nodes act as hubs or bridges connec�ng
different clusters. These nodes have higher than average connec�ons and can quickly route to many other
nodes, effec�vely reducing the path length between any two nodes in the network.
Node Behavior That Encourages Small-World Proper�es
Dynamic Connec�vity: Nodes may change their connec�ons dynamically, forming new links that act as
shortcuts. For example, in vehicular networks, a cab picking up passengers from different loca�ons creates
new links between those points.
Preference for Certain Connec�ons: Nodes might preferen�ally a�ach to well-connected nodes, known as
'preferen�al a�achment', which creates hubs that reduce the average path length.
Mobility and Flexibility: In vehicular networks, mobility allows for constant changes in the network topology,
with vehicles entering and exi�ng the system and crea�ng temporary paths between various nodes.
Example - Vehicular Networks:
Vehicles such as cabs, buses, and even private cars with ride-sharing services can become nodes within a
vehicular network.
Cabs and buses connect disparate geographic loca�ons as they follow their routes, offering a form of transport
between various nodes (i.e., stops or des�na�ons) and linking different clusters (neighborhoods, districts,
ci�es).
When cabs and buses transport individuals between these nodes, they are effec�vely crea�ng shortcuts that
can drama�cally reduce the steps needed to connect any two points in the network.
Ride-sharing services enhance this effect by dynamically determining routes based on passenger demand, thus
op�mizing the network for even shorter paths.
The addi�on of smart technology and IoT devices can further op�mize routes in real-�me, responding to traffic
condi�ons, passenger requests, and other environmental factors, enhancing the network's small-world
proper�es.
In conclusion, the small-world phenomenon in a network like a vehicular network is enhanced by nodes that
are highly interconnected locally but also include key nodes or behaviors that introduce shortcuts, thereby
reducing the average path length across the en�re network. These shortcuts are crucial for crea�ng the small-
world phenomenon and can arise from dynamic behaviors and structural proper�es of the network itself.
1 / 1 ptsPergunta 3
Sua Resposta:
What fundamental studies or experiments have contributed to our understanding of the small-world
phenomenon? Can you describe their findings and methodologies?
1. The Milgram Experiment (1967)
Study: Stanley Milgram's "small-world experiment" aimed to test the six degrees of separa�on concept.
Methodology: Milgram sent packages to randomly selected individuals in the Midwest, asking them to forward
the package to a friend or acquaintance who they thought would bring the package closer to a final target
person in Massachuse�s. Each "hop" was recorded un�l the package reached the target.
Findings: Milgram found that it took, on average, about six hops for the package to reach the target, which
supported theidea of six degrees of separa�on. However, not all le�ers reached the final des�na�on,
highligh�ng network imperfec�ons.
2. Wa�s and Strogatz Model (1998)
Study: Duncan J. Wa�s and Steven Strogatz developed a mathema�cal model to explain the small-world
phenomenon.
Methodology: They started with a regular la�ce (a ring of nodes each connected to its nearest neighbors) and
randomly rewired some edges to introduce long-range connec�ons. This process was controlled by a
parameter, which represented the probability of rewiring each edge.
Findings: The study showed that even a small number of random connec�ons could significantly reduce the
path lengths between nodes, crea�ng the small-world effect. They also noted a high clustering coefficient,
meaning that if A is connected to B and C, then B and C have a higher likelihood of being connected.
3. Barabási-Albert Model (1999)
Study: Albert-László Barabási and Réka Albert proposed a model to explain the emergence of scaling in
random networks.
Methodology: They used a growth and preferen�al a�achment mechanism, where nodes are added to the
network one at a �me and preferen�ally a�ach to nodes already well connected.
Findings: This model led to the concept of "scale-free" networks, which contain hubs that are highly
connected and play a crucial role in the network's topology, influencing the small-world phenomenon.
4. The Columbia Small World Project (2003)
Study: Peter Sheridan Dodds, Roby Muhamad, and Duncan Wa�s conducted an online version of Milgram's
experiment.
Methodology: Over 60,000 par�cipants from 166 countries sent e-mails to acquaintances to reach one of 18
targets in 13 countries. The progress of each e-mail was tracked.
Findings: The median number of intermediaries was between five and seven, providing further evidence of the
small-world phenomenon. However, the success rate of completed chains was low, sugges�ng that social
network structure is essen�al in understanding the phenomenon.
5. Facebook Study (2011)
Study: Facebook conducted research using its massive social network to test the six degrees of separa�on
theory.
Methodology: The study used all ac�ve Facebook users (721 million at the �me), calcula�ng the average path
length between all pairs of users.
Findings: They found the average number of acquaintances separa�ng any two people was not six but 4.74,
sugges�ng that the world is even more connected than previously thought, likely due to the rise of online
social networks.
1 / 1 ptsPergunta 4
Sua Resposta:
The small world phenomenon, o�en called "six degrees of separa�on," describes the idea that people in
extensive social networks are usually closely linked to one another through only a few intermediaries. In
essence, it means that you can establish a connec�on with almost anyone on the planet through a rela�vely
short series of social connec�ons.
How does the small world phenomenon relate to the spread of informa�on, rumors, or diseases in a
popula�on? What insights does it offer in these contexts?
The small-world phenomenon has significant implica�ons for the spread of informa�on, rumors, and diseases
within a popula�on. The underlying structure of social networks, characterized by short path lengths and high
clustering, means that en��es (whether informa�on, gossip, or pathogens) can disseminate rapidly and widely
throughout the network. Here are some insights into how the small-world phenomenon relates to these
contexts:
Informa�on and Rumor Spread
Rapid Dissemina�on: Due to the small-world nature of social networks, informa�on or rumors can travel
quickly from person to person through rela�vely few intermediaries.
Influence of Hubs: People with many connec�ons (hubs) can accelerate the spread as they act as
broadcas�ng nodes, reaching large numbers of people directly.
Clustered Transmission: High clustering means that once informa�on enters a �ghtly-knit group, it can
circulate extensively within that cluster before moving on to another.
Viral Poten�al: The combina�on of clustering and shortcuts created by hubs can lead to viral informa�on
spread, where a piece of informa�on becomes widespread rapidly if it crosses certain thresholds of sharing.
Disease Spread
Epidemic Outbreaks: In terms of epidemiology, the small-world network model helps explain how
infec�ous diseases can spread quickly through popula�ons, leading to outbreaks or epidemics.
Super-Spreaders: Individuals who are highly connected or who have significant mobility (like frequent
travelers) can become super-spreaders, analogous to hubs in informa�on networks.
Containment Challenges: The small-world phenomenon makes containment of diseases difficult, as the
pathogen can traverse the network through the few degrees of separa�on, bypassing localized
containment measures.
Modeling and Predic�on: Understanding the small-world proper�es of social networks is crucial for
modeling disease spread and predic�ng poten�al outbreaks, allowing for more effec�ve public health
interven�ons.
Implica�ons for Public Policy and Communica�on
Targeted Interven�ons: By iden�fying and targe�ng hubs or clusters, interven�ons can be more effec�ve,
whether it's stopping the spread of misinforma�on or vaccina�ng against a disease.
Informa�on Campaigns: In the context of public informa�on campaigns, leveraging the small-world
network structure can op�mize the spread of important public health messages or other cri�cal
informa�on.
Crisis Management: During a crisis, understanding the small-world dynamics can inform strategies to
quickly disseminate alerts and updates to avert or mi�gate disasters.
Limita�ons and Considera�ons
Structural Variability: It's important to note that not all social networks perfectly fit the small-world model,
and real-world complexi�es o�en introduce variability that can affect the spread.
Behavioral Factors: The willingness of individuals to share informa�on or adhere to health guidelines can
significantly influence the spread, regardless of the underlying network structure.
Pontuação do teste: 5 de 5
Anterior Próximo
Detalhes do envio:
Tempo:
27
minutos
Pontuação atual: 5 de 5
Pontuação
man�da:
5 de 5
Graduação Presencial Assíncr…
Página inicial
Teams
Atendimento
Avisos
Tarefas
Fóruns
Biblioteca PUC
Minas
Notas
Pessoas
Programa
Testes
Módulos
Avaliação CPA
PUC Carreiras
Conta
Painel de
controle
Cursos
Grupos
Calendário
Caixa de
entrada
Histórico
Studio
Ajuda
https://pucminas.instructure.com/courses/156029
https://pucminas.instructure.com/courses/156029/quizzes
https://pucminas.instructure.com/courses/156029/quizzes/400686
https://pucminas.instructure.com/courses/156029/quizzes/400686/history?version=1
https://pucminas.instructure.com/courses/156029/modules/items/3384600
https://pucminas.instructure.com/courses/156029/modules/items/3384612
https://pucminas.instructure.com/courses/156029
https://teams.microsoft.com/dl/launcher/launcher.html?url=teams&type=meetup-join&enableMobilePage=true&suppressPrompt=true&tenantId=14cbd5a7-ec94-46ba-b314-cc0fc972a161
https://conteudo.virtual.pucminas.br/canvas/crm/index.php?user_sis_user_id=1078276@sga.pucminas.br&course_sis_course_id=sga_54419_128_2023_2_1525101&course_id=156029
https://pucminas.instructure.com/courses/156029/announcements
https://pucminas.instructure.com/courses/156029/assignments
https://pucminas.instructure.com/courses/156029/discussion_topics
https://conteudo.virtual.pucminas.br/canvas/biblioteca_puc/index.php?user_sis_user_id=1078276@sga.pucminas.br
https://pucminas.instructure.com/courses/156029/grades
https://pucminas.instructure.com/courses/156029/users
https://pucminas.instructure.com/courses/156029/assignments/syllabus
https://pucminas.instructure.com/courses/156029/quizzes
https://pucminas.instructure.com/courses/156029/modules
https://conteudo.virtual.pucminas.br/canvas/avaliacao_cpa_2018/index.php?user_sis_user_id=1078276@sga.pucminas.br&course_sis_course_id=sga_54419_128_2023_2_1525101
https://carreiras.pucminas.br/
https://pucminas.instructure.com/profile/settingshttps://pucminas.instructure.com/
https://pucminas.instructure.com/courses
https://pucminas.instructure.com/groups
https://pucminas.instructure.com/calendar
https://pucminas.instructure.com/conversations
https://pucminas.instructure.com/accounts/1/external_tools/33?launch_type=global_navigation
http://help.instructure.com/