Search Engines and the Application of Graph Theory (Page Rank)

The search engine Google uses a method to provide ordered listings called Page Rank. Page Rank is fundamentally a concept of graph theory by using IP Addresses (your domain names  address) as your vertices , and hyperlinks located on that site as edges.

In this form of graph theory, edges have weight. This means that the more weight for each edge, they are more likely to be traveled on if you think of the bridges example. In the case of search engines the higher weight accumulated for each website determines where it will be put in the order of search results.

What is interesting is that If a person knew exactly how the Page Rank algorithm worked then they could potentially have their website placed higher on google’s search results.

You can read more about it (Here on Cornell’s Blog)

Biology Through Graph Theory

A DNA strand made up of multiple genes

Picture Link: http://www.extremenaturalhealth.com/wp-content/uploads/sites/90/2014/04/Genes.jpg

 

The article I found describes how biologists can use graph theory to find out more about DNA structure and gene mutation to more accurately determine how genes and DNA strands work. Through microscopic networks, biologists can figure out how diseases spread through infected people and how genes mutate and affect other genes using this kind of math, where the graph expresses molecular structures. I found this article to be very interesting, as it takes math I didn’t think would connect to biology at all and actually makes it into a possible mathematical solution to genetic problems and disease control!

Google Maps and Graph Theory

It’s likely that you have used Google Maps before. However, it’s also likely that you don’t know how Google Maps finds these paths for you to take. Turns out they use some graph theory.

Initially, Google weighs the edges that would be part of a map, usually by either time or distance. A major part of the way they are able to find these shortest paths is by using an algorithm that actually comes up later in our book: Dijkstra’s Algorithm. That really rolls off the tongue (It’s dike-stra by the way). As given by the book, to use Dijkstra’s Algorithm:

1. Mark the ending vertex with a distance of zero. Designate this vertex as current.
2. Find all vertices leading to the current vertex. Calculate their distances to the end. Since we already know the distance the current vertex is from the end, this will just require adding the most recent edge. Don’t record this distance if it is longer than a previously recorded distance.
3. Mark the current vertex as visited. We will never look at this vertex again.
4. Mark the vertex with the smallest distance as current, and repeat from step.

Here’s an example of this algorithm being used visually:

http://www.opentextbookstore.com/mathinsociety/2.5/GraphTheory.pdf

https://motherboard.vice.com/en_us/article/4x3pp9/the-simple-elegant-algorithm-that-makes-google-maps-possible

Graph Theory

https://phys.org/news/2017-12-hidden-bridge-quantum-graph-theory.html

This article talks about graph theory as a solution to Quantium physics.  Although we have only applied graph theory to bridges and transportation routes, from this article you can see how this form of mathematics is found everywhere.  Even when discovering more about a science we would not even think related.  Since this discovery of the link of these two math subcategories, scientists are doing a lot more research on how they link together and why. Needless to say graph theory is everywhere around us, even in things we would least expect.

Building Transport Systems Through Graph Theory

While doing a little research on Graph Theory I found an interesting connection that we’ve already touched upon in class. While the Bridges of Konigsberg were a simple example of Graph Theory, there are many other complicated transport systems that have been built on the foundation of this same theory.  This article, in particular, brought up the use of telecommunication systems as networks that would need specific links, like cables, in this case, to connect the “nodes”. The article really strips all of the information back to the basics, so it is extremely easy to understand. It’s a pretty short read as well, so if anyone is at all interested in this kind of thing, I’d definitely recommend it!

https://transportgeography.org/?page_id=5976

The Art Gallery Problem – Helping Heist Movies and D&D Campaigns Alike

Sure, George Clooney is a good-looking man but did he consider the art gallery problem in Ocean’s 11? …No seriously, I have no idea. I’ve never seen the movie. 🙁

I was curious about graph theory and what prominent topics are involved in it. Perhaps one of the most interesting and practical problem I found in the Wikipedia entry for graph theory is the art gallery problem (also see here).

To sum it up: The problem asks us to consider how many security guards we’d need to carefully monitor an art gallery. This depends on many variables such as the size and shape of the art gallery.

Marianne Freiberger for Plus Magazine, summarizes the mathematician S. Fisk’s answer to this conundrum as:

..[Y]ou never need more than n/3 guards (so that’s 9/3 = 3 guards in the example in the figure). That’s true for any simple polygon with n vertices, no matter how complicated and irregular it looks.”

Which is pretty amazing.

So next time you’re watching your favorite heist movie or thinking about starting a heist campaign in D&D, consider the art gallery problem!

Graph Theory in Chemistry

I found a page of a book written by a Romanian organic chemist. This page mentions how chemists use graphs like the ones we used in class to demonstrate covalently bonded compounds. After reading this page, I remember doing something very similar to this in my high school chemistry class. The edges of the graph represent covalent two-electron bonds and the vertices of the graph represent atomic cores (valence electrons are not included in these graphs).

https://pubs.acs.org/doi/pdf/10.1021/ci00047a033

Gerrymandering

While looking up gerrymandering I came across a site that showed how the U.S looks before and after the county lines were distorted. I found this interesting because you can see how much influence State legislatures have in decided the districts. The picture i added shows the difference between the original county lines and after when they were changed to lean left or right. 

https://www.washingtonpost.com/news/wonk/wp/2016/01/13/this-is-actually-what-america-would-look-like-without-gerrymandering/?noredirect=on&utm_term=.031221fcbf0a

 

I also remembered watching a John Oliver episode about Gerrymandering and though it was very interesting to see the affects. It is 20 minutes long but it is kind of funny and flies by. Please watch .

https://youtu.be/A-4dIImaodQ

Sealed Bidding with United Airlines

“Auction overbooked airline seats” was an article that was written a year ago when United Airlines had the incident of dragging a passenger off the plane because more passengers showed up for the flight then there were seats available. The author of this article suggests a method that allows passengers to volunteer their seats at check-in. He suggested that sealed bidding method would be the best way to entice passengers to give up their seats if they chose. If they bid the lowest then they will give up their seat, but will get compensated and the airline would arrange other travel amenities. This will help show what each passenger believes is the best value of their seat, as well as bring in more bids for the airline so there is less of a chance for the airline to get overbooked on a flight.

http://www.baltimoresun.com/news/opinion/oped/bs-ed-airline-auction-20170510-story.html

 

Approval Voting in US elections

I came across an article that talks about how presidential elections should be held by using approval voting. Currently, our voting process consists of citizens individually voting for who they want to win, then the Electoral College in each state votes based on the votes that state received for each candidate; in order to win, the candidate must receive the majority of electoral votes. This system of voting has been used for a significant amount of time, but whenever a large portion of voters disagree with the outcome, the topic of changing the voting system to make it “more fair” is discussed. My understanding of this voting method is that each election has different outcomes, it does not favor one party over the other, however, it does make it extremely difficult for a third party candidate to win a states electoral votes.

 

Changing the voting method to approval voting does not seem like it would be the best option to me, although this article thinks otherwise. The article talks about how the plurality method is a “really bad” method to use and how approval voting gives candidates a more equal opportunity to win. As we learned in class, the plurality method does not satisfy two criterions—the Condorcet criterion and the IIA criterion. However, I do not believe changing to the approval voting method would be the most effective change. The approval voting method does not satisfy the majority criterion or the Condorcet criterion. This means that both methods only satisfy two out of four criterions in Arrow’s Fairness Criteria.

 

If people are arguing to use the most “fair” option of voting, it seems as though Copeland’s Method should be their method of choice. This method meets the majority, Condorcet, and monotonicity criterions. It would be considered the most fair because it meets three out of the four requirements on Arrow’s Fairness Criteria.

 

It is interesting to me that people decide that the method for voting should change when they do not like the outcome, yet when their candidate wins, they are happy with the method. There is no perfect method for voting; therefore, there will rarely be an outcome where everyone is happy. It is interesting to compare different methods and their outcomes in elections because ultimately, depending on the method it is possible to get a different winner each time a different method is used. For now, I personally believe that we should keep our voting methods the same and educate ourselves more on how we vote and who we are voting for in order to try and better our political system with each election.

The link to the article is below incase you would like to read it.

https://electology.org/blog/making-approval-voting-reality-us-elections