Networks

Supply Chain Network Expansion in the Current Day and Age

The world with its vast 8 billion people and millions of industries is all interconnected through many nodes and edges. People, businesses, governments, organizations, etc. are all connected. With billions of connections that span distances of tens of thousands of miles, how is the world so efficient at providing supply chain solutions to businesses and industries. In this post, I would like to look into the connectivity of the world through international supply chains and routes. Mostly about its development and how it has changed in recent years in terms of social and economic networks.

The term supply chain dates back to the earliest civilizations. In Mesopotamia, supply chains were built to support the shift from agricultural-only societies to more technologically developed civilizations. In addition, one major supply chain route is the famous Silk Road, which connected Europe with the rest of Asia for thousands of years. This increased cultural diffusion and supported economic growth for all major civilizations at the time. If you want to look at this in terms of nodes and edges, each city that is connected on the Silk Road such as New Delhi, Beijing, Jerusalem, Egypt, etc. is a node, and the routes that connect them as the edges. The distance traveled is immense and the distance between nodes may vary depending on the geological location of the city route, however, these nodes and edges connected the world for the last millennia and led to future technological growth for interconnectedness.

Looking to the current day and age, our supply chains span worldwide with millions of routes, nodes, edges, and major hubs for industries. With the expansive development of shipping, air freight, and safer road networks, the world is connected in a much better light and allows for industrial and economic growth for all. One change to the node and edge network in the current day and age is that there are billions of nodes since almost every person has their own supply chain. People can now order items through their phones, send emails across the world, and sell clothes from their closets directly to other consumers. These changes reflect the current state of the supply chain network and showcase the vast connectivity that it has had in recent years.

Some challenges related to the current supply chain network is that there are many factories that are struggling with production as well as labor shortages that are slowing down shipment times all across the globe. Changes are constantly being made to the network such as implementing new nodes and hubs for transportation, utilizing newer technologies, and increasing the labor force for supply chain corporations. Over time, new nodes/hub cities will be created and major changes will be made to the supply chain to support the expansive growth of the world.

Data and Inspiration: https://unctad.org/publication/international-supply-networks-portrait-global-trade-patterns-four-sectors

Braess’s Paradox: Exploring its Limitations in a City Like Los Angeles

Braess’s Paradox, a captivating theory in traffic and network dynamics, suggests a counterintuitive scenario where adding roads to a transportation network can lead to increased congestion. This concept has intrigued experts in various fields, from mathematicians to urban planners. However, its relevance in a sprawling city like my home of Los Angeles becomes significantly diluted when considering the complexities of network structures and Nash equilibria.

Originally conceptualized by Dietrich Braess in 1968, this paradox challenges the conventional belief that expanding road infrastructure always alleviates traffic congestion. At its core, it hinges on the behavior of drivers in a network: each driver selfishly chooses their route aiming to minimize personal travel time, but collectively, these individual optimizations lead to a suboptimal overall traffic flow.

However, when analyzing a metropolis such as Los Angeles, several factors diminish the applicability of Braess’s Paradox:

1. Network Dynamics and Nash Equilibria: In a real-world scenario like Los Angeles, the network’s complexity significantly deviates from simplistic models used to illustrate Braess’s Paradox. Networks are multifaceted, and drivers adapt their routes based on various considerations, creating a Nash equilibrium where no driver can benefit from unilaterally changing their route. This equilibrium, influenced by multiple variables, challenges the paradox’s oversimplified assumptions about individual driver behavior.

2. Dynamic and Multifaceted Driver Behavior: Los Angeles drivers exhibit diverse behaviors influenced by an array of factors, such as real-time traffic updates, weather conditions, and social norms. Instead of solely seeking the shortest travel time, drivers consider multiple variables, resulting in a complex decision-making process that doesn’t conform to the assumptions of Braess’s Paradox.

3. Geographical and Infrastructural Constraints: The physical landscape of Los Angeles, with its geographic barriers like mountains and canyons, poses limitations on road construction and expansion. Unlike the theoretical models, implementing new roads may not always be feasible due to geographical constraints, altering the predicted impact on traffic flow.

4. Comprehensive Transport Strategies: Los Angeles’ approach to traffic congestion involves more than just road expansion. Initiatives encompass public transit enhancements, prioritization of alternative modes like cycling and walking, and the implementation of strategies such as carpool lanes and congestion pricing. These interventions influence driver behavior and disrupt the simplistic assumptions underpinning Braess’s Paradox.

While Braess’s Paradox offers valuable theoretical insights into traffic dynamics, its practical application in sprawling metropolitan cities like Los Angeles encounters significant limitations. The interplay between network complexities, Nash equilibria, geographical constraints, and unique transportation strategies creates a dynamic system that surpasses the simplistic assumptions of the paradox.

Sources:

https://en.wikipedia.org/wiki/Braess%27s_paradox

https://vcp.med.harvard.edu/braess-paradox.html

Unraveling Social Ties: A New Perspective on Edge Strength Inference

Discussed throughout the early portion of this class, Strong triadic closer is a concept which determines the nature of the interconnectivity presented to us via a network graph. I would like to end my time in this class by discussing the paper “Relaxing the strong triadic closure problem for edge strength inference’. This paper showcases the intersection between emerging graph theory and the previously established concepts from the class. Many networks are binary in vie; either individuals are connected via a tie, or they are not connected at all. While paths may exist bridging the world together, disparate portions cannot research each other. 

This blog post delves into a paper published on January 17, 2020, that proposes a novel approach to understanding what total graph connectivity may be like even with disparate parts. 

 

The background:

The paper builds on the Strong Triadic Closure (STC) property, a concept rooted in sociology. STC posits that if person A has strong ties with both B and C, then B and C must also be connected, forming a triad. Previous work by Sintos and Tsaparas (2014) introduced the STC property for edge strength inference, formulating it as an NP-hard maximization problem. This basically meant that the number of strong edges would be maximized within the  graph to ensure interconnectivity, increasing the prevalence of strong connections and relationships throughout the entire approach.  However, such an approach faced the following implementation challenges. 

1.), it was NP-hard, requiring approximation algorithms. 2.) it often resulted in multiple optimal solutions, leading to arbitrary strength assignments. What this means is that if an optimal structure could not be determined wherein the relationship between node c and node b was considered, the node strength would be assigned at random. 

 

The new stuff!

 

Jumping back to the paper at hand, this paper extends the previous work by proposing a series of Linear Programming (LP) relaxations. The key contributions are as follows:

 

1. Relaxing Integrality Constraints. The first relaxation allows edge strengths to take continuous values between 0 and 1. This not only makes the problem polynomial but also introduces three-level edge strengths—beyond binary distinctions. In doing so, the nuances of the structure can be determined, allowing for future work regarding balanced graph implementations of enemies and friends (you guys remember that stuff? I’m sad it wasn’t on the final, i was good at it ;( )

 

1. Alternative Objective Function Instead of solely maximizing the number of strong edges, the paper suggests maximizing the sum of weights in all triangles. This alternative objective aligns more closely with the empirical distributions of tie strengths in real datasets.

 

Thus the paper reveals that the proposed LP relaxations have desirable properties. The first relaxation guarantees a half-integral solution, offering a meaningful three-level edge strength assignment. The second one is less obvious: it presents a more accurate view of reality,not everyone is trying to maximize their strong times all along. The countenance for this by the paper allows us to move forward with this information inclusively. 

 

Practical Implications

 

The experimental evaluation conducted by the authors showcases the strengths of their proposed approach. By relaxing the rigid constraints of STCbinary, the new method adapts better to real-world scenarios, questioning the validity of relying solely on the STC property for edge strength inference.

 

Conclusions

This paper gives an insight into how the ideas we have talked about in class have continued to develop. I look forward to seeing my kids networks textbook in 20 years, maybe thell have a copy of this new research somewherein it? By leveraging LP relaxations, the approach introduces more flexibility, allowing for a finer-grained inference of edge strengths. Theoretical insights and empirical results suggest that this methodology could be a valuable addition to the toolkit of social network analysts, providing a more realistic portrayal of the intricate fabric of social connections. 

 

Shout out to the professors!

 

Source:

https://link.springer.com/article/10.1007/s10618-020-00673-0

 

Networks are around us more than we think

Admittedly, when I first registered to take this class, it was to fulfill a requirement towards the Information Science major, however, the longer I continued in the course, the more I came to realize that networks are all around us. Although we may not consciously think about them, networks govern every interaction that we make. For every new friend we make through a mutual friend, a strong triadic closure is completed. For every cup of coffee purchased during this finals week, a series of auctions and other market arrangements determined the pricing of everything from the coffee bean, to the espresso machine, and even the hourly wage of the barista. And for every TikTok video or Instagram post liked while taking a break from studying, an algorithm based on the theories of networks and how they form the basis for popularity decides what content you’ll see.

Final Exam Scheduling – A Perfect Matching Problem

The Matching Problem

Cornell University has over 2,500 final exams and final deliveries to schedule over the Fall exam period, consisting of 8 days between December 8th – December 16th. Exams can occur at 9:00am, 12:00pm, 2:00pm, 4:30pm, and 7:00pm, for a sum of 5 exam slots per day per 9 days, or 5 * 9 = 45 slots. The university faces hard constraints such as the amount of testing rooms available every day. Additionally, they face soft constraints, such as keeping courses typically taken together on different days if possible.

In keeping the exams of similar classes on separate days, the University faces a unique challenge, as not accounting for this may result in a significant number of exam conflicts that could require rescheduling. For example, let’s say INFO 1200 and INFO 1300 are both courses with exams that students are likely to take together. They may try to avoid a potential exam conflict between these two courses by assigning weights based on the probability that a student taking INFO 1200 or INFO 1300 is in both classes. If there are 500 students taking INFO 1200, 600 students taking INFO 1300, and 300 students taking both courses, we can determine the probability that a student is taking both courses by dividing the number of students taking both courses by the total number of students in both courses. To avoid counting the 300 students in both classes twice, we subtract them from the total count of 1100, giving us an overall total number of students as 1100 – 300 = 800. As a result, the probability of a randomly selected student from these courses being in both courses is 300/800 = 0.375.

The probability can be assigned as a weight to INFO 1200 and INFO 1300 that encourages the University from assigning these two courses on the same day. In comparison, consider INFO 1200 and PHYS 1101, which are unlikely to have much crossover between the two courses. If INFO 1200 has 500 students and PHYS 1101 has 400 students, and there are 50 students in both courses, then we can calculate the probability as before. This results in a probability of 50/850 = 0.059. Using this probability as a weight, we can see that PHYS 1101 would be a much better option to schedule on the same day as INFO 1200.

As we can see, there are many challenges that must be faced in this perfect matching problem in order to make sure that buildings are not assigned to two courses finals on the same day and time, and that similar courses are not scheduled next to each other. We can set up a much more simple version of this to show what this process may look like for the university.

A Simplified Example

In our problem, we will have a total of 8 exams across 4 majors, and 2 days with 2 testing times each. There are 2 testing buildings, so it is possible for 2 exams to be scheduled at the same time as long as they are in separate buildings. However, we will add a hard constraint such that exams from the same major cannot be scheduled at the same time. For example, if there is a math exam on Monday at 2:00pm in Barton Hall, there cannot be a math test occurring at the same time in Statler Hall.

We have the following testing time slots:

• Monday 2:00 pm Barton Hall
• Monday 2:00 pm Statler Hall
• Monday 4:00 pm Barton Hall
• Monday 4:00 pm Statler Hall
• Tuesday 2:00 pm Barton Hall
• Tuesday 2:00 pm Statler Hall
• Tuesday 4:00 pm Barton Hall
• Tuesday 4:00 pm Statler Hall

We have the following exams:

• INFO 1200
• INFO 1300
• CS 2110
• CS 2800
• PHYS 1101
• MATH 1010
• MATH 1920
• CHIN 1101

To create a perfect matching, we can begin by assigning INFO exams and CS exams at the same times, since there are two of each and will be affected by our constraint:

• Monday 2:00 pm Barton Hall – INFO 1200
• Monday 2:00 pm Statler Hall – CS 2110
• Monday 4:00 pm Barton Hall
• Monday 4:00 pm Statler Hall
• Tuesday 2:00 pm Barton Hall – INFO 1300
• Tuesday 2:00 pm Statler Hall – CS 2800
• Tuesday 4:00 pm Barton Hall
• Tuesday 4:00 pm Statler Hall

This leaves the following exams:

• PHYS 1101
• MATH 1010
• MATH 1920
• CHIN 1101

Which we can apply in a similar manner:

• Monday 2:00 pm Barton Hall – INFO 1200
• Monday 2:00 pm Statler Hall – CS 2110
• Monday 4:00 pm Barton Hall – MATH 1010
• Monday 4:00 pm Statler Hall – PHYS 1101
• Tuesday 2:00 pm Barton Hall – INFO 1300
• Tuesday 2:00 pm Statler Hall – CS 2800
• Tuesday 4:00 pm Barton Hall – MATH 1920
• Tuesday 4:00 pm Statler Hall – CHIN 1101

As we can see, there is indeed a perfect matching with these exams, such that two exams from the same major are never occurring at the same time.

Conclusion

Universities face this challenge on a much greater scale, with numerous exams, days, time slots, and buildings. In order to improve the likelihood of a perfect matching, universities may apply a weight scale as mentioned above such that courses with final exams and a high likelihood of crossover are largely preferred to be placed at different times, but not required to be. This makes it easier to find a perfect matching when there are so many exams to schedule and so many crossover courses, as a hard constraint like ours would make it very unlikely to find a perfect matching. Weights would decrease the likelihood of conflicts and increase the likelihood of a perfect matching, but would not necessarily result in zero conflicts. This task of assigning exams across finals week shows a prime example of how perfect matching can hide behind the logistics of our lives, presenting unique challenges to those who discover them.

Sources

Cornell University Fall Final Exam Schedule https://registrar.cornell.edu/exams/fall-final-exam-schedule

Homophily and Murder

Apart from Info 2040, there are other classes that discuss relevant topics about connectivity and networks. In Info 2450 Communication and Technology, homophily is described as the tendency for people with similar values and goals to become acquainted with each other. This can often lead to partiality when the network is homogenous. As we reaffirm our beliefs with people in our chosen networks, algorithms on social media also filter information to our preferences. However, it does not necessarily make the information less diverse. Understanding this homophily in networks can lead to applications to real-life situations surrounding public and social dynamics. Recognizing the patterns can lead to effective marketing strategies, policies…and even the key to murders. 

“Of the homicides that occurred in 2017 for which supplementary homicide data were received, the relationships of the murder victims to their offenders were as follows: 1,867 victims (12.3 percent) were slain by family members; 1,469 victims (9.7 percent) were murdered by strangers; and 4,236 victims (28.0 percent) were slain by “other known” offenders. The offenders were not known for 7,557 murder victims (50.0 percent).” ([1] FBI, Expanded Homicide)

Although serial killers often do not discriminate with their killings, there is usually a motive behind choosing specific victims. Most serial killers are male, and many victims are from marginalized, underrepresented groups. However, there is a fair amount of victims that are slain by those that they know.  Upon closer inspection of the victims, there is often a pattern of homophily related to the killings. Through investigations, it can be discovered that the murderer is a part of the same social network or even part of the family. 

Individuals who murder usually have a clear motive for choosing the victim. This means that they can share a background, lifestyle, or even a friend group. These relevant similarities can lead to a more targeted suspect pool. Understanding this provides context clues on potential reasons or conflicts that could have resulted in the crime. Similarities or affiliations between the killer and the victim can also lead to insights into their relationship. While profiling is based on assumptions, homophily within networks is a strong indicator of potential motivations for the crime. Detectives may consider homophily in crime scenes to probe and explore group dynamics. 

Homophily can lead to suspecting those similar in proximity, socioeconomic factors, and culture. Proximity does not only refer to closeness in geographic distance but also relationship-wise. Examining not only the nearby residence, but the inner social circles of the victim, is a helpful starting point. As for socioeconomic factors, it is helpful to note if the victim was struggling with money due to financial disputes or rivalry. Analyzing financial records may reveal potential connections to the victim’s murder. Lastly, cultural rituals, practices, and symbols could indicate the perpetrator’s background. Cultural homophily can shape the behavior and norms of an individual, which can leave traces in a crime scene. Even religious affiliations can play a role in the motivations behind the crime. Furthermore, in the technological age, homophily can also exist within digital networks. Analyzing digital platforms and footprints can reveal communities of interest that the user engages in. Although it is important to avoid stereotypes, homophily in networks can be an approach to gaining a beginning understanding of the workings of a murder. 

[1] https://ucr.fbi.gov/crime-in-the-u.s/2017/crime-in-the-u.s.-2017/topic-pages/expanded-homicide#:~:text=Of%20the%20homicides%20that%20occurred,4%2C236%20victims%20(28.0%20percent)%20were

Networks and the Future of Society

Today I found three New York Times articles that do a great job of connecting what we’ve learned in class to our world in 2023. The articles – “Has the Age of Mass Protest Actually Achieved Anything?”, “The Future of Social Media Is a Lot Less Social”, and “What Even Is a Social Network Anymore?” – give real-world examples that really emphasize the importance of information cascades in our society, specifically how people either adopt or reject certain behaviors that they perceive.

The first article is about mass protests and ties in with our exploration of information cascades. Just as we learned how individual decisions can lead to greater patterns, David Wallace-Wells illustrates how individual actions in protests accumulate to create significant social movements. This phenomenon reflects the concept of information cascades, where individuals, influenced by the actions of others, join in, thereby amplifying the movement. This is more relevant than ever with the advent of social media; it is like the marble example we talked about, except at a much faster pace.

The second article discusses the future of social media becoming less social and relates very much to our discussions on network structures and their evolution over time, like with the behavioral cascades. Most of the article focuses on the shift in social media from broad-based platforms to more intimate, conversation-driven spaces echoing the dynamics we studied about network evolution and the role of individual nodes (users) in shaping the network’s structure. This shift signifies a move from a broadcast model to a more clustered, community-oriented model, reflecting our class discussions on how real-world networks evolve and adapt over time.

The third article aligns with our class’s exploration of network theory’s fundamentals. The article’s exploration of how social networks have evolved from purely social spaces to platforms encompassing news, commerce, and more parallels our discussions on the multifaceted nature of networks. It underscores the idea that networks are not static; they are dynamic systems that adapt to the changing needs and behaviors of their users. Again, our principles from class apply here, but more advanced models are going to be required because of the exponential growth of our social media networks.

 

Articles:

https://www.nytimes.com/2023/11/22/opinion/does-protest-work-bevins.html

https://www.nytimes.com/2023/04/19/technology/personaltech/tiktok-twitter-facebook-social.html

https://www.nytimes.com/2023/08/25/style/social-media-apps.html

Braess’s paradox and google maps

One aspect of this class I really loved was when we talked about various paradoxes. When we talked about Braess’s paradox I think it is so interesting to think about the evolution of how it can be applied to our lives. 200 years ago when people were traveling on foot or by horse they had to think carefully about what route they should take from point A to point B. If they found out about a new route/road they could take because everyone was talking about it, they may assume it’s better. Even though adding roads/routes oftentimes makes people worse off. Braess’s paradox probably occurred very frequently when people did not have access to the same technology as we do today. In the present, GPS apps like waze and google maps have pretty much prevented Braess’s paradox from occurring in a directional context because it shows you the most efficient route almost instantaneously. I wonder how other paradoxes and concepts we learned this semester will change with the evolution of technology.

“In college, weak ties are stronger than you think”

Max Feldman’s article in The Michigan Daily, “In college, weak ties are stronger than you think,” sheds light on the often-underestimated value of weak ties in a university setting, particularly at the University of Michigan. Feldman discusses how acquaintances, those individuals we know casually from classes or dorms, play a significant role in enriching the college experience. This perspective aligns closely with the concepts explored in our class. Strong ties represent our close, personal relationships, while weak ties refer to less intimate, more sporadic connections.

Feldman’s article underscores the importance of these weak ties in the broader context of university life. He argues that casual interactions with acquaintances can significantly boost our mood and sense of belonging, especially during stressful times. This idea resonates with the Weak Tie Theory from our class, which suggests that weak ties can be more beneficial than strong ones in certain aspects, like networking and exposure to diverse perspectives. Feldman’s insights encourage us to value and cultivate these weak connections, recognizing their potential to enhance our university experience and open doors to new opportunities and communities.

In college, weak ties are stronger than you think

The many degrees of Erdos – and Bacon!

An interesting phenomenon in the world of mathematics networks is something called the Erdős number. Paul Erdős was an influential mathematician from Hungary who published over 1,500 mathematical articles and collaborated with hundreds of mathematicians and scientists from all over the world. Erdős himself is assigned an Erdős number of zero. A direct collaborator of Erdős on an academic paper would be assigned a number of 1. Someone who collaborated with that collaborator then would be assigned the number 2. A certain author’s Erdős number is one greater than the lowest Erdős number of any of their collaborators. This principle can be used to examine the network of mathematicians worldwide.

The concept of the Erdős number isn’t restricted to the world of mathematical research, however. It is better known by a more familiar application – analyzing the network of actors. The Bacon number, also known as the 5 Degrees of Kevin Bacon, captures an actor’s closeness to Kevin Bacon. It isn’t intuitive to think that we are only a few degrees of separation away from Hollywood’s most famous stars, yet we can use network analysis to challenge our perceptions and beliefs. There are even crazy-sounding permutations of these rules, including the Erdős – Bacon number, which indicates an individual has both acted in a professional film and published a mathematical article. Natalie Portman has an Erdős – Bacon number of 7!!

« go back — keep looking »