Just from the two beginning weeks in class and the wide range of blog posts, it is clearly evident that networks play a dominant role in all of our lives. Referencing the latest post about research in the neural field, we could say that networks are “hard-wired” into our systems. Merely cataloguing some of my daily activities illustrates the important role networks play in my life. I got some exercise by running on a treadmill (a network of electrical circuits and connections), took the bus to the mall (a transportation network), and purchased some laundry detergent (a network of the chemicals that comprise the formula). This short list illustrates that networks not only take on a variety of forms, but also that they necessary components of life. A question that might arise is: what happens if a network is “shut down” for political, practical, or ethical reasons? This is the exact question addressed by the article: Kidney Exchange: A Life-Saving Application of Matching Theory.

 A depiction of the kidney showing transsection of the renal artery and the renal vein as seen in a live donor transplant.

Credit: © Brian Evans

Here’s the background. In class, as well as any introduction to economics course, we learn that the market for a good is just a giant network of consumers and producers. The “bridge” in this giant network can be thought of as the price of the good or service. In a very rudimentary sense, the price serves this bridging mechanism by connecting buyers and sellers who might have otherwise not interacted. There’s no need for further review of economics to state that the price allocation mechanism is good, but far from perfect. For some goods and services, prices cannot serve as the ultimate allocative force for ethical and equity reasons. A prime example of such a “good” is a kidney. According to the article, in 2005 alone, 60,000 people will be in need of a kidney transplant while only about a quarter of those people will find a donor. The National Organ Transplant Act makes it illegal to acquire an organ for “valuable consideration,” which precludes a traditional price allocation of kidneys. It’s not necessary to go into detail why this act is founded on rational principles because a market for kidneys could cause greater damage than good. So now that our market (network) is shut down, how do we address the issue of the shortage of kidney donations? Economist Alvin Roth, Tayfun Sonmez and Utku Unver have come up with a novel solution: create a new type of network.

These economists along with Francis Delmonico and Susan Saidman have developed a kidney exchange network database to help abate the kidney shortage dilemma. Roth and others likened the solution of the kidney shortage problem to a problem faced by many college students in dorms. Some have dorms, some don’t, and some are willing to trade. The same issue appears in kidney donations. For example, let’s say that my brother needs a kidney donation. I have two kidneys and can live with only one, so I go to my doctor and see if I can be his donor. I get the blood test and find out that either we do not share the same blood type or that he will have an immune reaction to my kidney. Our doctor puts him on the wait list and forgets all about the prospects of my being a live kidney donor. However, with the implementation of this kidney exchange program, the story doesn’t stop here. My kidney might not be compatible with my brother, however, it may be compatible with many other persons in dire need of a kidney. Better yet, they might know someone whose kidney is not compatible with them but it completely compatible with my brother. Under the new system, the doctor would not just disregard my prospects of being a donor as before. He/she would submit my medical information into a giant kidney database. My data would be analyzed to find the best match for my kidney and in return, my brother would use the same database to find the best match for his kidney. The article notes that in addition to its possibilities of increasing live kidney donations, the exchange program provides incentives to compile the best information on each donor and recipient thus reducing the amount of organ rejections.

There are, of course, obstacles to the program’s full success. One necessary condition is that the transplant has to occur simultaneously. Imagine the future of the program if I say that I would donate my kidney then conveniently change my mind after my brother receives his transplant. Despite this limitation on the program, in September 2004, the Renal Transplant Oversight Committee approved the establishment of a donor tracking system for kidney exchange. The program is still in its initial phases, but Roth proposes that the program could increase the number of live donations by 2,000-3,000 per year. As of the 2005 article, exchanges existed in New England, Massachusetts, Pennsylvania, and Michigan.

The kidney exchange program discussed in the article provided a tangible example of many of the concepts taught in class as well as ideas in The Tipping Point and chapter 2 of the “Networks” text. First of all, it is clearly evident that this database serves as a gatekeeper between a donor and donee. Let’s say the match for my brother is a 35 year-old businessman from Michigan. The edge, in this case, is the kidney donation. I speculate that even if my brother were to interact with this man, the notion of a possible kidney swap would fail to come up in conversation. However, my brother is linked to the database through my kidney donation, the 35 year-old businessman is linked via his kidney donation and the database is what determines our ultimate interaction. Also, a supplementary concept discussed at the end of chapter three is relevant to the kidney exchange. This is the concept of “betweeness.” According to the text, a node “b” is between two other nodes “a” and “c” if it lies on some shortest path between “a” and “c” and is not equal to them. “Betweeness” is a measure of for how many unordered pairs of nodes this occurs. Clearly, the kidney exchange database would have a “betweeness” value in the thousands. Such a property is of integral importance when considering the temporal element of kidney transplants. By reducing the distance of the connection between a donor and donee (hence the wait time for a transplant) this program could save many lives based on time savings alone. Finally, the kidney exchange database provides a good example of a social-affiliation network discussed in chapter 2 of our text. Social affiliation networks consist of edges representing relationships as in a social network and edges representing participation in activities as in affiliation networks. For example, there is an edge connecting me to my brother and our doctor that represents a social relationship. In addition to these edges, there is an edge that connects me to the database linking me to the kidney donation activity. Imagining what this network would look like graphically is quite a feat especially because there is a clear directional component to it. However, the article does provide a diagram of the main idea behind the kidney exchange program. This program is just one example of how networks can be used not only to model the way the world is now, but also change it for the better. In The Tipping Point, Malcolm Gladwell describes Robert Horchow as one of the ultimate “connectors” in the social realm. I believe it’s clear that this database can serve as the ultimate connector for those in need of kidneys.

Link to Article

http://www.nsf.gov/discoveries/disc_summ.jsp?cntn_id=104404&org=NSF

S2N Media for the National Science Foundation An exchange performed because of blood type incompatibility. The husband of Recipient 1 donates to Recipient 2 and the adult child of Recipient 2 donates to Recipient 1.

Credit: S2N Media

In class, we’ve recently discussed various types of global networks containing giant components: social networks, computer networks, and economic networks. But one of the largest and most effective giant components is sitting right behind your eyes. The brain is the most connected network your body, and consequently the most complex. It’s estimated that the human brain has 100 billion neurons– more than 15 times the global population. Brains produce the most intricate of behaviors, but are composed of single units which are comparatively quite simple. So, the intelligence of the system is a product of the network that neurons are organized into.

Neuroscience has attempted to understand some of how data is processed and behaviors produced in the brain by isolating circuits within the neural network. But of course, while interesting, this is extremely limited. As demonstrated in class (1/28/08), the behavior of a group of three nodes can have implications for the entire network. If a triangle of nodes prefers to be “balanced,” then the global network will tend towards either a single cohesive group, or two separate groups.

Similarly, the connectivity of a single neuron has implications for the connectivity, and function, of the entire brain. The next step is to map the entire brain, as a complete network, and use this as a basis for our understanding.

To the left is the ALTUM machine, which will automatically make thin slices of a mouse brain . A picture will then be taken, and the image sent to a computer which can compile a 3D image of the brain. This is part of a project by Jeff Lichtman, a professor at Harvard university. If the project is successful, a full scan of a mouse brain will contain petabytes of information– a scale at which Google servers operate on.

Complete brains have been mapped out before. A complete map of the 300 cell nervous system of C. elegans is commonly used in neuroscience research. But mapping out a mammalian brain such as that of the mouse, with whom we share a great deal of our genome, is considered by many to be the Human Genome Project of neuroscience.

For more about the ALTUM machine and connectonomics, see the WIRED article on which this blog post is based.

Read the rest of this entry »

In an article published last summer in the New England Journal of Medicine, Christakis et al investigate the spread of obesity as a social contagion. Using the dataset from the Framingham Heart Study, they performed a longitudinal study (1971-2003) to study how social networks contribute to individual’s body mass index, or BMI. The researchers discovered multiple clusters of obese persons in the community, and that these clusters were separated by about 3 degrees of separation. A person’s risk of becoming obese increased significantly when he or she had a friend, a spouse, or a sibling who became obese. There was no discernible effect from geographic neighbors, which suggests that physical environment (e.g. sidewalks, parks, crime in one’s neighborhood) may mean much less to the development of obesity than who you associate with.

The spread of obesity through these networks suggests that social norms matter. Individuals may be sensitive to eating and exercising habits of their closest friends, and mimic their behaviors. Malcolm Gladwell argues in the Tipping Point that humans are highly sensitive to the context of their surroundings. Obesity as a social contagion may spread similarly through networks as contagia of fashion or crime.

The accompanying animation illustrates several important points that we’ve covered in class:

1. It shows a large component with several unconnected graphs changing dynamically over time.
2. It demonstrates triatic closure, as obese individuals become more tightly connected with one another. The network becomes more dense over time.
3. It illustrates the concepts of nodes, bridges, edges and the fact that some individuals are more connected than others.

Professor Theodore Lowi of Cornell University’s Government Department often reiterates the theme of not living virtual lives, whether political or…sexual, as he puts it in lecture. He recalls a time when Cornellians left the classroom, took buildings over by force, and marched for change.

Nevertheless, the virtual realm has become one of the battlefields against genocide. In fact, the Genocide Intervention Network (GI-Net), started by Swarthmore College students, is not only at the forefront of raising awareness of modern day holocausts, but hosts fundraising events for UN-African Union peacekeepers by selling trendy “Save Darfur” wristbands. GI-Net uses popular social networking websites such as Facebook, MySpace, LiveJournal and YouTube as vehicles in spreading the anti-genocide message, advocating the cause and organizing events. The donations, now amounting to half a million dollars, go towards both protecting the civilian population and supplementing the UN’s humanitarian relief effort.

The structure of these social networks provides the ideal connection between edges for information to diffuse amongst various nodes. This is particularly true because the structure is made explicit in online “friend lists” where groups and activities can be shared with hundreds of acquaintances with just a click of the mouse. If only a dozen people act upon the message (c.f. Gladwell’s Connectors), then the information will continue to cascade around the network (e.g. Schelling’s Herding). Given the interconnectivity of these online networks and small world phenomena, it may take as few as six steps to reach a great deal of active users–socially active high school and college students.

Lowi’s skepticism of whether virtual concern will be mirrored in real life action is answered by the existence of five hundred schools with a STAND chapter (A Student Anti-Genocide Coalition). Although virtual technology and social networking sites now play a key part in facilitating information about the world’s crises, they cannot replicate the formal structure of international peacekeeping organizations nor understand fully how genocide victims suffer.

Social Networking helps Peer-to-peer lending loan $300+ million in 2 years

Above is an article about the facilitation of loaning and lending through internet social networks. In light of ever increasing loan rates, peer-to-peer lending has grown popular in moving money from individual lenders to those looking for competitive loan rates. The biggest name in peer-to-peer lending, Virgin Money (formerly known as Circle Lending), has handled over a hefty $200+ million. Online Banking Report (a research firm) expects that peer-to-peer lending will amass as much as $1 billion in funding by as early as 2010. There is also speculation that funding can top $9 billion in less than a decade in 2017. For those Facebookers reading this blog, peer-to-peer lending has even found itself in Facebook via facebook apps.

The concept is simple. Sites such as Virgin Money facilitates the loaning of money between individuals for a small service fee (as low as less than 1% for lenders and less than 2% for loans). From there, individual lenders and borrowers are free to exchange money. Borrowers win in two ways: They have an alternative to conventional loans and they choose from a large market of peer-to-peer lenders. Meanwhile lenders can earn about %7-18%.

The reason why I share this article is that the rise of peer-to-peer lending looks like triadic closure in action. It can be said that we are all have strong ties to banks. I keep most of my money at the Bank of America. Meanwhile, my bank uses that money to loan to clientele. Those clients and I have strong ties to the bank. By triadic closure, it would be natural that I have a tie with at least one of those clients taking a loan from my bank. After all, why don’t I just lend directly to those clients? Aside from the gross oversimplification of the situation, peer-to-peer lending is the answer to this question.

Welcome to the course blog for INFO 204. This is a course which will cover how the social, technological, and natural worlds are connected, and how the study of networks sheds light on these connections.

Topics include: how opinions, fads, and political movements spread through society; the robustness and fragility of food webs and financial markets; and the technology, economics, and politics of Web information and on-line communities.

The content on this blog viewable by the public. However, only the course staff and enrolled students are allowed to comment or post to this blog. We have also preserved the posting privileges of the students enrolled in this course last year since we believe some of the could be interested in making meaningful contributions to the discussions this spring. All students enrolled in this course are required to participate in updating this blog. The guidelines can be found here.

In order to comment or post to this blog, students must have an NSDL account and register that account with ExpertVoices. You can follow the directions for registration here. Be sure to register with ExpertVoices from this blog. Once an account has been created and registered with ExpertVoices, click on “Request Post Permission” on the top right corner of this blog.

In keeping with course privacy guidelines, no student will be required to make their true identity public as part of this activity. Students are strongly encouraged to use a nickname when posting or commenting. After being granted post permission, click on your name on the top right corner of the main page of this blog (you must be logged in first). This will take you to a page where you can edit your profile. Type in a nickname in the appropriate field and click on “Update Profile”. After your profile is updated, you can then select your nickname from the drop down menu labeled: “Display name publicly as:”, and then click on “Update Profile” again.

Please also fill in the fields for your name and email address. While this information will not be publicly displayed, we require this in order to assign grades.

The interface for updating this blog is fairly straightforward. Please refer to this help page if you are having difficulty. If your problem persists, feel free to email me at bistra@cs.cornell.edu.

Even though class is over, the topic of networks still appears everywhere I go.

For instance, this website, walk2web, which constructs graphs which constructs a complex graph from an initial input URL, which attempts to link the different websites that are somehow related to each other (hyperlinks, etc).

Try it, you’ll be surprised at the complexity of the graphs!

Pharmacologists can be well-connected.

John J. Abel is regarded as the founding father of pharmacology, after forging the field in the late 19th century. Along with 18 colleagues, he founded American Society of Pharmacology and Experimental Therapeutics (ASPET), and is most famous for his work isolating epinephrine and crystallizing insulin. Abel published nearly a hundred papers.

Check out “Six degrees of pharmacology: Game ranks researchers by proximity to field’s founder,” an article from news @ nature.com by Jill U. Adams. You can go through the Cornell library, or if you are a nature.com subscriber go here.

As the article explains:

These papers are shared with a total of 27 co-authors, who, in the new game, are assigned an ‘Abel number’ of 1. Those 27 scientists co-published with at least 278 individuals (who get an Abel number of 2), who in turn published with at least 3,000 more (Abel number 3s).

In celebration of their 100^th anniversary in 2008, ASPET is now trying to find the Abel numbers of the rest of the pharmacology community (see ASPET website).

Despite the rivalry that resulted at the Experimental Biology meeting where this game was played, in reality these Abel numbers are more about a person’s connections than any creditable reputation. It is a family tree of pharmacologists, one that gives the field some comradeship and gives ASPET a good hundred years of traceable history.

This game is similar to the Six Degrees of Kevin Bacon game (see earlier blog post), or more similar to the game of mathematicians, who have an Erdös number that shows how close they are to the Hungarian mathematician Paul Erdös, who was famous for his huge number of collaborators (over 500) and for being one of the most prolific publishers of mathematical papers in history (around 1,500). Read about The Erdös Number Project, a project with a LOT of interesting detail.

The Erdös number study has an abundance of data and discussion available thanks to the head of the project, Jerry Grossman at Oakland University. In the Erdös numbers distribution, almost every mathematician with a number has a number of less than 8, with only about 2% higher, and none over 15. This goes to show the connectivity of the network of mathematicians.

As represented partially in the image above, the data starts with a collaboration graph (C) of about 401,000 authors, with edges that represent co-authors of papers. Without including multiple edges between two author who collaborated multiple times, the graph has 676,000 edges, with the average number of collaborators per person equaling 3.36. As in many connected graphs, there is a large group of well-connected authors. As the website explains:

In C there is one large component consisting of about 268,000 vertices. Of the remaining 133,000 authors, 84,000 of them have written no joint papers (these are isolated vertices in C). The average number of collaborators for people who have collaborated is 4.25; the average number of collaborators for people in the large component is 4.73; and the average number of collaborators for people who have collaborated but are not in the large component is 1.65.

There are then 5 people, including Erdös, with more than 200 coauthors. These well-connected people are the celebrities that make the graph bigger, and the interconnections smaller. The approximate average distance between two vertices is 7.64. As average path lengths are small, and the “clustering coefficient” of this C graph is high (0.14), the graph can be considered one of Duncan Watt’s “small-world” graphs.

      Erdös number  0  —      1 person

      Erdös number  1  —    504 people

      Erdös number  2  —   6593 people

      Erdös number  3  —  33605 people

      Erdös number  4  —  83642 people

      Erdös number  5  —  87760 people

      Erdös number  6  —  40014 people

      Erdös number  7  —  11591 people

      Erdös number  8  —   3146 people

      Erdös number  9  —    819 people

      Erdös number 10  —    244 people

      Erdös number 11  —     68 people

      Erdös number 12  —     23 people

      Erdös number 13  —      5 people

The median Erdös number is 5; the mean is 4.65, and the standard deviation is 1.21.

How amusing that one of Erdös’s specialties was actually… graph theory. I wonder if either of our own professors might have a notable Erdös number? There are two Kleinbergs on the list of 8674 people with a distance of 2 or less, but alas, no Jons.

As has been discussed over the course of this class, online advertising has shown to be very profitable for search engines basing the advertisements shown to keywords. Keyword-based advertising is a win-win for the search companies and the advertisers; because people are seeing results that are customized to what they are looking for, the ads are more likely to be clicked on and let to the advertiser’s web page, and thus these advertisers are more willing to pay for popular key words. It would also seem that the user could be alright with this paradigm; they see ads that are more relevant. However, the user has not really been given a choice as to whether or not they want their actions influencing the ads they see, and this is raising some big concerns with individual privacy.

However, keyword search may only be the beginning in customizing to individuals in order to turn a bigger profit. “The information collected by many Web sites — browsing histories, search histories, wish lists, preferences, purchase histories — is amassed and manipulated in ways consumers never know about.” (New York Times) The result is that a large repository of information is being collected that tells much about how each individual acts and is considered an invasion of privacy to many.

One solution that has been suggested is grant ownership of consumer-related information to the people, and let them decide whether or not they wish to share their information with marketers. In her blog Identity Woman, a woman named Kaliya, who describes herself as “saving the world with user-centric identity.” Should individuals have the right to hold private what can be easily collected on the web and manipulated in order to be more profitable? I think that there will not be enough of a call for privacy until enough people believe that their clickstream data is their own, and not the property of those who collect it.

http://blog.tooreal.net/articles/gmail/

Back in 2003 when web-based email services were dominated by Hotmail and Yahoo! who offered a paltry 4MB of space for the average ‘free’ user, web-mailing was such a pain I hardly used my Yahoo! account. April 1 2004: Enter Gmail, with a 1GB storage limit, a fresh user-friendly interface with several neat features, and a restricted invite-only beta testing stage that tickled and piqued the curiosity of those that missed out. The cascade has begun.

Today, three years down the road, Gmail has become a phenomenon. While I lack the numbers indicating the present market share, it seems to me that many people have switched over from Yahoo! and Hotmail to Gmail. I know I did. What made this cascade possible?

In class, it was mentioned that for a cascade to take place, the value of the new technology has to outweigh that of the previous technology. With other webmail services having a good ten years under their belt, it seemed impossible for Gmail to have any success in squeezing into the webmail market and uprooting the already entrenched services. However, with new exciting features, a ‘cool’ interface, and some commendable marketing, Gmail has forced its own cascade. 1GB of storage space left Yahoo! and Hotmail’s 4MB and 2MB offerings looking laughable, and the latter two quickly moved to offer an improved capacity in their webmail services. Grouping messages into tags is another ingenious feature that made navigating through those endless chain of emails a breeze. And the user friendly, and ‘cool’ interface (done in AJAX) just made the novelty of switching over really worth it — it looked great and navigating felt good. And the marketing strategy of keeping it restricted to an invite-only group of individuals just capped it off and made the exclusivity of this new webmail service another huge plus to its overall value. All these features made Gmail’s value soar spectacularly above that of Yahoo! and Hotmail, and it was no surprise that the cascade took off.