To view the image, go to http://movies.nytimes.com/pages/movies/index.html and click on “That’s Gratitude For Ya” under Multimedia. If the image has been removed, go to http://s7.photobucket.com/albums/y265/Berner6/.

The New York Times printed the above image on the front page of its Arts Section, Tuesday, February 27. The image depicts a directed graph compiled from this years Oscar acceptance speeches. There are two types of nodes. The twenty-four nodes with pictures represent an Oscar award winner; the twenty-five nodes with only text represent all of the people, places, and things that the winners thanked in their speeches. The edges of the graph are directed, originating from an Oscar winner node and terminating on a thanked node.

In analyzing the graph, the way nodes are connected, and the way nodes are organized, it is clear that without even reading who or what was thanked, there are distinctive types of nodes thanked. Twenty thanked nodes lie on the fringe of the graph, none totaling more than four terminating edges (“advisers and financers” on the middle right). One node lies closer to the middle and has seven terminating edges (“Everyone who helped make film” towards the bottom right). The group of nodes that stand out the most are the five in the middle, which range from thirteen to eighteen terminating edges. As a group, those five nodes more than double the number of speech mentions the other twenty nodes had (80 to 38).

One way to interpret the significance of a smaller group of thanked nodes dominating the rest is that those five have proportionally more importance to the movie and award winner. This seems to generally hold true, except for thanked nodes on the fringe, such as the film’s inspiration and financers, without which the film probably never would have existed and become successful. Also, family, a highly thanked node in the middle, is not inherently important to the success of a film, which contradicts the first interpretation. Another interpretation is that the five nodes in the middle represent high-profile people and things, such as the director of the film and the Academy itself, and thus received vastly more recognition at such a high-profile event like the Oscars.

http://www.cs.kent.ac.uk/pubs/2004/1931/content.pdf

Download PieSpy: http://www.jibble.org/piespy/

PieSpy is a freeware program that can be used to track interactions amongst users in an online chat room.  The software employs several methods to not only determine which users are interacting with each other, but also just how strong these interactions between the two individuals are.  It then generates a detailed mathematical model for the Chat Room Social Network.  The program uses three methods to achieve this.  First, it stores each individuals nickname in the chatroom, and when a chat post directly addresses someone, the two individuals participating in it are linked.  Secondly, the software uses the concept of temporal proximity.  If no message has been posted in several moments, and then two are posted close together, it is reasonable to assume that the second message was in relation to the first and thus the two individuals are connected.  Finally, the program employs the notion of “temporal density” when it analyzes messages.  What these means is that if n messages have been sent over a short period of time and only two users are involved in the sending, these two users are assumed to be having a conversation.  The program uses a setting of n > 5 for its “conversation” threshold.  The length of the line connecting two individuals is proportional to the strength of their ties, which shorter lines connecting those that are “stronger” in their linkage.

By tracking and evaluating the interactions between people in a chat room, PieSpy enables the user to construct elaborate social networks for groups of people.  Furthermore, by labeling the strengths of each edge, it allows some approximation of just who has power in a social network.  As discussed in lecture, those with a high centrality to a network or multiple strong ties exhibit more power than others in that network.  The program allows easy visualization of this concept.  Furthermore, each time PieSpy is run in the same IRC channel it bases its network off networks that have already been stored. This allows one to see just how the social network has evolved over time, providing insight into just how power shifts in an ever changing social network.

This article is one man’s attempt to explain network theory to his audience.  I found this particular blog by searching for “Triadic Closure”, and it caught my eye because he is explaining it to a rather unusual community.  The writer is an Associate Professor at Abilene Christian University (Richard Beck), and his audience is the Christian community.  The topics covered are the same as the first few lectures of this course.  He also refers to the book The Tipping Point, and the article The Strength of Weak Ties.  Using these sources he outlines the importance of weak ties, and the concepts of triadic closure.

            To make the material more relevant to his audience, he explains how connectors (people who have many weak ties) help the church achieve the goal of influencing the community, and spreading information throughout a network.  He also explains the role of connectors inside the church community as people who bring diverse groups together.  To summarize, I found this to be a thorough and easy to understand explanation of network theory.     

http://experimentaltheology.blogspot.com/2007/02/ecclesial-quotient-ecq-connectors-weak.html    

Ant hills, intercellular communication, human interaction… all consist of complex networks that cannot be described linearly (are high-dimensional), nor can they be easily understood or modeled. The study of such complex systems can be applied to a plethora of subjects, and Mark Smith, MD and Craig Feied, MD decided to apply complex system theories to, what else, the Emergency Room:

The Emergency Department as a Complex System – Mark Smith, MD and Craig Feied, MD

The Emergency Department (ED) system, as simply as possible, is an enclosed system comprised of the entrance and exit of patients. It gets more complicated when it comes to the details of each medical condition and treatment, the transfers of patients between people and rooms, the tests done, the paperwork… every minor decision that is made and unexpected event that occurs will completely change the path of a patient, and no two paths are ever the same. When picturing this, I think of random fractals, in which anything can happen as it grows into a complex, irregular, and multi-dimensional image.

 The ED may be more of a system of processes than a network, although it is possible to think about it like the networks we talk about in class. The nodes could be possible events that occur, and the edges would be the paths that patients may follow. Some nodes would be passed through often (everyone has to fill out forms), whereas rare accidents can call for a one-of-a-kind treatment that will only be on one patient’s path. Of course this web of events would be huge, as think about all the possible things that may happen in the ED. So perhaps we could think of it more as a sequence that is being created, where one thing leads to the next in a directed graph of events.

As in several of the networks discussed in class, the ED system is rich and complex, and often paradoxical. Similar to Braess Paradox in which an extra road increases travel time and decreases productiveness, the more complex the ED system is, the worse its operating state. It is important in an ED that there are not too many people to go through, or too many tests to be done. The ED system goes further beyond this paradox as it is to amazingly able to move between order and chaos and back again, often because of one seemingly-insignificant factor. An ED is sometimes a state of chaos when there are too many patients and too little organization. Yet sometimes this chaos will switch to a beautiful order; this is not order in the sense of calmness, but order that Smith and Feied refer to as “a humming complexity, a room resonance,” in which so much is happening but it all seems to be working well together as intended. This is the way of many complex systems and networks, in which one change or addition can either fix or completely disrupt the workings of the system.

In Smith’s and Feied’s attempt to train this beast that is the ED system according to the concept of complex systems, they offer several interesting theories. The main idea is increasing simplicity, which relates to the idea that less is better. As in most systems that need optimization, it is better to have less connections or steps. For example, in the case of the ED, the process of testing a patient’s blood can be reduced from 8 to 3 steps, reducing the nodes and the length of connections necessary.

In class we talked about the strength of connections, as well as their direction. Smith and Feied suggest that we use both of these as applied to the ED. They suggest that it is important to put value to each of the processes in ED care so as to better evaluate quality. This gets complicated, however, since some of the process scores need to be high (e.g. patient satisfaction, revenue, reputation), whereas some need to be low (e.g. turnaround time, complaints, costs, violations). They also suggest that each process needs a feedback loop that goes in the reverse direction of each process to check for error, making each process connection a two-way connection. This is much better than a global system of error identification that simply analyzes the end, rather then every step in between. Local evaluating connections allow for increased quality and awareness of places for improvement. If we were actually able to map out a particular ED, we could analyze the values of each connection with the feedback loops and find ways to improve various paths through the system.

There are some final ideas offered by Smith and Feied that I find very interesting. Their 80/20 rule states that putting in 20% of the effort required will bring about 80% of the return, so often it is important to avoid burdensome perfectionism and focus on small but significant change. This relates to their 85%/15% rule, which says that for a complex system it is important to find the most important 15% to change, as this is really the most you can conquer at a time. But as mentioned earlier, just a 15% change when done right can affect the system as a whole in just the right way. This is an interesting statement, and one that can probably be applied to many issues beyond the ED. When optimizing any system, it may be helpful to be in the pessimistic mindset that one can only affect a small portion of the entire problem, yet it is important to put as much as possible into that small portion because that makes all the difference.

Mapping out any network or system can often lead to clarity and show potential improvement sites. In the study of networks we like to believe that this is always the case, that we can visualize and understand any system of connections. Yet complex systems make things much more interesting, particularly when we are looking at a system such as an Emergency Department, where optimization can save money, time, and most importantly, lives.

In a previous post, rebelkingismyhero discussed a model of large scale networks called the random graph. A random graph/network is generated by connecting each pair of a number of vertices with some probability. This creates a graph with each vertex having the same connectivity or level of connectedness on average. rebelkingismyhero noted that the behavior of many networks in the real world do not seem to match this model.

I really enjoyed reviewing Barabasi and Albert’s paper “Emergence of Scaling in Random Networks” which expands the random graph model to allow for growth in the network. Previously the number of vertices in a graph was fixed at the outset of the simulation. Barabasi et al. tries to instead mimic real world systems which continuously expand. Their model starts with an initial number of vertices and then links a new vertex to some of the old vertices each time step. To determine which vertices the new vertex will attach to, Barabasi incorporates ‘preferential attachment’ i.e. a vertex is more likely to attach to a popular vertex that has many edges than an edge that has only a few. The networks that result are similar to well documented networks such as the web and citation patterns in journals in that they self-organize into a network with ‘hubs’ and have connectivity that follows a power law.

In class we have studied networks that are static. I find it interesting to think about how the networks we have used to study power imbalances would grow if we used Barabasi’s technique to expand the network. How would the network evolve if we allowed vertices with power below a certain threshold to ‘die’? Should we modify the definition of ‘preferential attachment’ to have a new vertex prefer connecting to powerful vertices rather than well connected ones? Perhaps the ‘balanced outcomes’ discussed in lecture would move away from extreme imbalances and instead move toward a more even distribution of power. I think that it is likely that individual ‘agents’ ‘ attachment preferences must be at work when you examine how social networks, trading markets, and even bone tissue grows. These personal preferences may influence the global behavior of a network. Likewise, perhaps the overall function of a network or the environment in which it grows dictates how a new vertex attaches to the rest of the network.

With the dynamic nature of the real world, studying how a network’s structure changes over time could be as important as studying the network’s structure itself.

http://www.nytimes.com/2007/02/26/technology/26fake.html?ref=technology

While there are many large scale social networks on the internet, none are as popular as MySpace.com. MySpace is a social networking website that allows users to build a network of friends, their own personal profiles, and access to groups, photos, music, videos, and blogs. As a result, it is pretty easy for someone to find information about a person’s lifestyle and character by simply looking at their MySpace page. In addition to displaying personal information, your MySpace page also shows a roster of all of your friends. The above link discusses a relatively new company, FakeYourSpace.com, which offers its users a way to enhance their personal MySpace accounts. For a small charge of 99 cents a month per “friend”, you can hire people to not only become your “friend”, but to post on your own personal page. The big perk about the addition of these newfound “friends”, is that they consist mainly of attractive models. Bryant Walker, founder of FakeYourSpace, says the purpose of his site is “to turn cyberlosers into social-networking magnets” by providing fictitious postings from attractive people.

FakeYourSpace creates an interesting dilemma to basic social networking theory. Generally, social networks consist of a group of people with each person represented by a node. Whenever two people have a relationship, whether it be due to friendship, romance, finance, etc., they are connected by an edge. However, the emergence of FakeYourSpace creates a significant amount of fake edges in the MySpace social network. By simply paying this monthly fee, a person can increase his social circle significantly without actually creating any new relationships. If one were to study the social relationships of a FakeYourSpace customer, they would surely encounter some problems. For example, if this fictitious “friend” posted several times on your MySpace page, you would conclude that the two have a strong relationship. If another one of your actual friends had similar behavior, you would also be able to classify the relationship as strong. As a result, you would conclude that these two friends would develop at least a weak relationship (triadic closure). However, since the FakeYourSpace “friend” doesn’t actually exist, no such relationship would ever develop. These new fake relationships would definitely be something that sociologist would have to consider if they ever wanted to study the interactions of MySpace users.

Facebook, evidently searching for masses of programmers to do their evil bidding, has actually found a great way to attract engineers at the same time as screening potential job applicants: programming puzzles.

Problem: (the full text of the long-winded setup to the problem can be found after the jump @ facebook)

Suppose you and 15 friends are at the cinema to see a long-awaited movie concerning velociraptors, but there is an extremely complex web of social relationships among your group and everyone has to sit together in a single row. As you’re from Cornell you’ll most certainly want to optimize the seating arrangement so that the you maximize the total social welfare of the entire group (i.e. maximize the sum of the payoffs incurred as a result of the seating arrangement).

The social relationships can be defined in a directed graph, with nodes representing people and directed edges representing how one a person feels about another. Types of relationships defined below such as “Mutual Strangers” can be extrapolated across the common edges shared by the relevant nodes. Also, for clarification, an edge which leaves a node1, representing person1, and entering node2, representing person2, and attached with a relationship type implies that person1 has that specific relationship type with person2 and seating them next to each other has a payoff that is dependent on this edge’s relationship type as well as the corresponding reversed edge’s relationship type. Hence, in terms of payoff, we can represent the problem as an undirected graph with each edge weighted with the payoff for seating two node/people adjacent to one another. Also note that this graph is fully connected, as every node has some type of a relationship with every other node.

Relationship types:·

Friends (F) · In A Relationship (R) · One-Way Crush (C) · Acquaintances (A) · Mutual Strangers (S) · Enemy (E) Each one-way pair between two people has only one of these relationship types, listed in the large array below.

Social enjoyment point values:

· 1 pt: Seating acquaintances next to each other · 2 pts: Seating two friends next to each other · 3 pts: Seating two people in a relationship next to each other · 1 pt: Seating someone next to their crush (if the crush is non-mutual) · 0 pt: Seating someone next to someone who has a crush on them · 4 pts: Seating two people together who have mutual crushes on each other · 0 pts: Seating someone next to a person they are strangers with · -4 pts: Seating mutual enemies next to each other · -3 pts: Seating two people in a relationship not next to each other and between them there is someone with a crush on one of them · -2 pts: Seating two people in a relationship not next to each other but between them there are no people with a crush on either of them · -2 pts: Seating someone not next to their crush but with that person’s significant other between them and the crush · -1 pts: Seating someone surrounded by strangers

Relevance:

Defining the optimum linear connection among a group of objects or people comes up pretty much constantly in everything from Operations Research to seating one’s extended family without fear of grievous bodily injury. Using the concept of social networking provides a nice framework to analyze the more complex graph theory going on under the surface, and maximizing the total payoff across a group is a serious topic in economics, with the small caveat that in this problem the people are not independent agents playing for their own welfare but rather being assigned to their seats. An interesting tangent would be to find the nash equilibrium if all the people were acting as independent agents.

So - This is Hard, NP-Hard

What we, in effect, have found is a nifty instance of a traveling salesman problem (TSP). This is a problem described by a situation where a salesman needs to visit a given set of cities (nodes), there is a cost traveling from one to another equal to the distance between the cities (weighted edges), and each node can only be traveled once. We can think about people as different cities and the relative payoff between two people akin to the cost of traveling between them. For this general problem, finding an optimal solution is np-hard (i.e. no fast algorithm which guarantees optimality and need to enumerate all solutions) and even asking if given a solution S is there a different solution S’ with a bigger payoff/less distance traveled is np-complete (i.e. good luck trying to find a solution to this).

An interesting graphical representation of this can be described as finding a Hamiltonian Circuit among a graph.

What do we do, then? Well, for more hefty solutions, this problem is mostly worked on by using a hybrid of two algorithm types: branch-and-bound, a linear programming (optimization) tool and a pruning method resembling a class of algorithms called Genetic Algorithms, which start off with a large search space then use a heuristic to prune some of the solutions that don’t seem to be promising.

For our small subset of the larger space of the problem, we can just use Branch-and-Bound:

1. We change the payoffs so that they are in the form of costs, with 0 cost on an edge representing 4pts of seating two mutual crushes together and 8 the cost of seating mutual enemies together
2. We divide the problem into a number of subproblems
3. To avoid computation over all possibilities, we try to find a viable solution first and use its cost as an upper bound for the optimum. All future calculations are terminated as soon as their costs exceed the costs of the upper bound
4. If a cheaper solution is found, its value is used as the upper bound
5. In this way, many calculations that would have to be done can be stopped early on.

Algorithm:

Enumerating all combinations, 16 seats with 16, 15, 14 … 2, 1 options for people in each seat if we iterate through them would leave us with 16! (16 factorial: 16 * 15 * … * 1) possible combinations, and analyzing 2.0923e+013 solutions for cost would work, although probably not get you a job at Facebook anytime soon.

So, what do we want?

1. Valid Seating: all 16 seats must be filled with different people
2. Maximum Payoff: sum of payoffs of social enjoyment values for adjacency is maximized

What do we have?

1. 16 nodes
2. 136 edges: can think of first node having 15 shared edges, second having 14 shared edges (as node to first already used), and so on

What do we do?

Using our branch and bound class of algorithm with our payoffs modified into a cost structure we come up with:

1. Choose an arbitrary start node as current node
2. Set upper bound to infinity (or max_double for geeks)
3. Choose cheapest edge between current node and an unvisited node, Add cost of edge linking the two to a value of currentCosts and repeat until either currentCosts > bound and sequence of nodes has not been completed or we have a valid seating
4. if currentCosts < upperBound, set this seating as the min seating and the upper bound as the cost of this trip
5. set the current path as something to never try again
6. Repeat until done or until we are satisfied enough with our solution

So, we can either wait for an optimum, which might take a while to find or we can terminate early with probably a pretty good seating arrangement. woohoo!

http://www.nytimes.com/2007/02/26/technology/26drill.html  

The attached New York Times article is titled; On Niche Dating Sites, Many More Women, and the subject of choice is online dating.  One of the issues brought up in the article is the uneven split of men and women visiting these sites; however, I want to take a look at the bigger picture.  Mentioned in the article is the fact that there are certain sites for almost anything you could imagine, from admirers of fuller women to sites based on religious affiliation.  These sites are more than just a way to meet people; they are the foundation of a network. 

One of the major components in a network to tip an epidemic is a Connector.  As described in, The Tipping Point, the connector is the type of person that knows an inordinate amount of people.  Beyond this, they would also send out emails or cards to every person they knew, and once they found out about something great they would share the knowledge with other people.  They might not be the most convincing like a Salesman, but they tell so many people that at least a few will take the advice, and then they will reach out to a few people, and we have began to tip an epidemic. 

The website facilitating the dating services is trying to be a Connector.  Depending on what kind of criteria you have depends on which website you go to, or as it would be, which Connector you get to know.  The Connector has its digital rolodex of names and birthdates and personality types; based on this, the website sends out emails saying that one person should check out someone from a list of people deemed to be compatible.  The epidemic on hand is a relationship.  Obviously not everyone will share the same relationship, but everyone will have a relationship based on compatibility and not just drunken hook-ups or borrowing a pen in line at the bank.  Using specific website as intermediaries for such large networks is remarkable, because the networks will continue to exist as long as people use the websites, and the websites will be knowledgeable Connectors trying to get to know as many people as possible and making suggestions to people every minute.

Homophily Theory

This link discusses the theory of homophily. This theory states that “most human communication will occur between a source and a receiver who are alike.” In layman’s terms it is the theory of why birds of a feather flock together. The article describes why this is: namely that communication flows more freely when the two people communicating are similar and we are more comfortable communicating with people who understand us better. The effort exerted when communicating with somebody who is not similar is much greater because it takes time and effort to have a mutual understanding and effective communication.

Homophily could probably be best studied in high school cafeterias by seeing who sits at what lunch table and what these people have in common. To connect the theory of homophily to what we have discussed in class isn’t cut and dry. In class we haven’t focused on social networks and homophily is all to do with this kind of network. Recently we have been discussing a network game that deals with splitting up a dollar and the power exerted by some members of the network. We can assume that the members of this network are pretty homophilous because of the ease in which they communicate. To split up a dollar by talking on Instant Messaging software in a couple of minutes implies that these people are able to communicate efficiently which in turn implies that they share things in common. The most obvious trait these people share is language. If nodes “a” and “b” speak English but node “c” speaks Yiddish, chances are that “b” is going to choose “a” to split this dollar with.

Game theory may help Tatas encounter CSN

Two prominent Indian steel companies, Tata Steel and Companhia Siderurgica Nacional (CSN) , are amidst a raging bid battle for Corus. Principles of game theory are drawn from both sides as each company devises its own strategy in the ascending bid auction that this business interaction has turned into. Tata’s strategy is simply to continue increasing its bids in small increments until the other companies drop out or it reaches its value. Unlike a private, individual ascending bid auction, however, Tata must consider the additional factor that the price of their bid may eventually destroy the combined stock price and perhaps force them to scamper for leverage in funding the transaction. CSN, on the other hand, must decide if Corus is worth the extra bid price synergistically.

The strategies of the two companies are obviously contingent upon the basic structures of game theory discussed in class, that following an ascending bid auction, the parties’ best strategy is to bid their respective true values in the auction. What’s interesting about this case is that it is presented in a business context where the “value” that, for example, a contending company places on another company must be considered with the weight of synergism and the possible effects on its own stock value along with those of the rival companies. Alternately, the lingering tragedy of the “winner’s curse” is very real in light of failing options coupled with “winning” the auction itself. In addition, its ultimate goal is to outdo its competition in business so opportunities to effectively cripple rival finances are not overlooked. In short, each company has the potential to guess at opposing companies strategies in business outside of the auction itself to determine how far to push a bid, thus creating great complications on top of the basic rules of game theory.