Have you ever gone to the movies and worried about who you’re going to sit next to?  This comic illustrates the common dilemma moviegoers face when filling the theatre aisles.

www.xkcd.com/173

The complex relationships between each pair of people in a group can be reflected in an acquaintance graph, such as the one shown above in the comic. Most people in such a network are usually acquainted with a majority of the group.  Consequently, a problem arises when each person can sit next to at most two people.  The question is: how do you convert a regular acquaintance graph (one where each person can be connected to an unlimited number of people) to a linear graph (where each person has an edge to a maximum of two people) while achieving maximum social enjoyment for each person?

In constructing our linear graph, we shall assume that maximum social enjoyment is achieved if each person is sitting next to the person they like most out of the group.  Here is one possible method of constructing such a linear graph.  1) In the regular acquaintance graph, place a value on each side of the edge, representing how much a particular person likes the person on the other side of the edge. 2) Now, look at each node and circle the maximum value it has towards a node (in case of a tie, circle all the maximums). 3) Eliminate any edges which do not have any circled values.  This should give us a simplified acquaintance graph (Note that the new graph can consist of more than one connected component). 4) If the graph is linear, we are done.  If not, the problem boils down to finding a path within from one node to another that traverses all the nodes within the connected component exactly once.   This is called a Hamiltonian path (for more information see: http://en.wikipedia.org/wiki/Hamiltonian_path ).  5) The resulting Hamiltonian path is our linear graph.  (Note: there are some cases in which a Hamiltonian path does not exist.  However, we shall assume that group dynamics usually support Hamiltonian paths, because of the way friendships naturally unfold.)

This is a very simplistic approach towards constructing linear graphs, where many nuances have been overlooked.  Also, a different definition of maximum social enjoyment can be used.  However, this method is useful because of its simple approach, and will give a good result in most cases.

In class we began talking about how Google ranked their pages, but did not get into the details of how any of this is performed underneath the surface.  I became interested in how this was actually carried through and I found some interesting finds.  According to Wikipedia’s (http://en.wikipedia.org/wiki/PageRank) article on PageRank, ranking pages is actually a system of equations using probability theory to solve page rank for the universe of web pages.  It has been said that every page, when it is created, starts at the same value as every other page did when they started out, and through time the pages converge to their rank.  This way each page starts with the same “initial” probability.  Through their complex algorithm, the page ranks get updated over time.  The factors for increasing the page rank come from the things we have discussed in class: in-links, out-links, keyword’s on pages, etc.  Here is a simplified picture of a web, and how page rank is determined .(http://en.wikipedia.org/wiki/Image:Linkstruct2.svg).  Some discussed problems with this strategy are that is favor’s old pages (as they have accumulated higher probability over time), and the ability to spoof the system to return a false page rank, and thus a tainted search.  Google tries to monitor this by ignoring pages with obviously bogus page ranks.  Not only is this PageRank system being used to rank web pages in search engines, but it is branching out elsewhere.  It is being used to rank scientific journal entries, and academic departments.  This system of PageRanking is being used on many other forms of informational networks other than the web.  As it becomes more refined, I think the way we search can only improve due to this use of PageRank.

References : Wikipedia

The semantic web is the target of a great deal of skepticism, but some projects are starting to make use of its principles to some of the most valuable resources on the internet even more valuable.  DBpedia, a part of the LinkingOpenData project, connects wikipedia with a number of other sources such as MusicBrainz, Project Gutenburg, flickr wrapper, and more. One of the most valuable assets this provides to wikipedia is a much more powerful search tool. DBpedia’s websites explains, “Wikipedia currently only supports keyword-based search and does not allow more expressive queries like “Give me all cities in New Jersey with more than 10 000 inhabitants” or “Give me all Italian musicians from the 18th century.”  In class, we have talked in depth about network structure, and it is clear that DBpedia is working to fill in some structural holes in the internet.  By interlinking these previously disconnected data sets this resource is clearly adding value to the web for the user.Links: DBpedia , LinkingOpenData 

I found this paper a while ago through another blog I read a lot, Gizmodo. It talkx about how members of Facebook and MySpace are divided by their real-life social status. Facebook tends to cater more towards what author calls “good” kids. These are college-bound, preppy  teenagers. MySpace users are usually part of the lower class society, people who are often classified as geeks or freaks. The author also talks a little about the impact of these two websites on the military. MySpace is banned by the military, but Facebook is not. What makes this point interesting is because MySpace is primarily used by soldiers, and Facebook is used by officers. Soliders are often lower class undereducated individuals, while officer usually come from a higher social group with more education.I felt this paper had a lot of ties to the ideas we talked about earlier with balanced networks. In the early days of these two social networks, Facebook was closed to the general public, so most people only had MySpace. Essentially, in the beginning there was only one giant unstable network. Slowly, facebook opened to college students, and started creating a network system, increasing stability. Many high schools were eagerly awaiting acceptance into college so they could join the new network. Finally, once Facebook opened its doors to the general public, everyone who was not part of the so called “MySpace crowd” was able to move, and the network is now essentially stable (at least on the internet). It’s a pretty interesting paper, and well worth a read through.Viewing American class divisions through Facebook and MySpace

The following information was explained by Kate Ehrlich of IBM Research during her talk to the Information Science department on February 22, 2008. Details are copyright IBM.

In engineering projects, communication is essential between people who are working on related tasks. Similar to this idea is the idea of triadic closure, which states that people with a friend in common are more likely to become friends themselves. Software engineering projects provide a unique example to study because the links between engineering tasks (such as program files and pieces of software) are clearly defined and analyzable. These program files (known as software artifacts) inherit, include, require, and otherwise interact with each other, creating a network of relations. Also, the relationships between people can be determined by examining emails and surveying team members.

Kate Ehrlich’s team at IBM used the following model to graph the network of a software development team. The model includes two types of nodes and three types of edges. Artifact nodes are linked to each other by task dependency edges, people nodes are linked to each other by coordination edges, and people nodes are linked to artifact nodes by task assignment edges (see Figure 1).

Figure 1: Socio-Technical Network Model

The resulting “socio-technical network model” can then be analyzed, looking for triadic closure and coordination gaps. When examining the graph, pairs of people who are working on dependent artifacts are identified. If there is a communication edge between the two people, they are said to be working in coordination, otherwise a coordination gap is identified (see Figure 2). Using this method, the entire graph can be analyzed and the extrapolated data can be used to determine where coordination gaps are so that remedial actions can be taken.

Figure 2: Coordination Gaps

Let’s face it, after hearing about Spitzer’s adventures at The Emperor’s Club a couple of days ago, the first website most of you visited was not CNN.com, but MySpace - I know I did. After spending a couple (ok, give me more credit than that - 15) minutes looking at “Kristen’s” bikini picture, a thought crept into my mind. How does one go about finding a prostitute named something other than Cinnamon, Velvet, or (my personal favorite) Foxy Roxy (courtesy of Kuma Charmers - “the hottest exotic strip club in the Finger Lakes region”)?

According to http://ap.google.com/article/ALeqM5gcl1re05K9b6bMBCQGikphgD6n6gD8VBFTDG1 (by Hillary Rhodes), Internet technology helps link up filthy rich politicians with $4300 callgirls. Online prostitution utilizes the Web as a social and an information network, similarly to Facebook and Google. The information network component of prostitution advertising comes in the form of online ads. A search for “bleep-bleep-bleep” on Google prominently displays links to “bleep.com”, “Hot-wet-bleep-bleep-and-tight-bleep.net”. In this way, escort businesses promote their products on the Web through online advertising, as discussed in class.

The second facet of the Web that these “technostitutes” utilize to recruit clients - according to Rhodes - is the social networking aspect. “It’s commercial, but it’s also social, so people do really form relationships” - says Audacia Ray, one of Rhodes’s interviewees. The author gives examples of websites (http://www.bigdoggie.com) where clients can rate the escorts. Higher-rated escorts usually receive more money for their services, as they create higher demand. This is analogous to how search engines work, where higher-ranked searches are more visible to the user and are thus visited more often. Of course, PageRank is different from Big Doggie’s algorithm in that the former is automated, and highly-ranked pages contribute more to the rank of the pages they link to, whereas Big Doggie leaves it to the user to rank the “product.”

In these ways, the escort business and the Web synergetically work together to make the world a better place. Web as an information network helps hard-working women advertise their services to a wide audience. Just like other businesses, escort services bid for advertising spots on Google and Yahoo searches. Moreover, for the “sex connoisseur” such as Mr. Spitzer, social networking websites such as Bid Doggie provide a rating service so that the client can more easily pick out his dream (or nightmare, if that’s what you are into) girl. In this way, today’s prostitutes utilize the structure of the Web as an information and social network - as discussed in class - to sell themselves in the same way a clothing company would sell itself as the best clothing store there is.

Digg Labs Swarm is a visualization that displays the most popular/most frequently viewed news articles on digg.com and shows how readers connect from one article to the next. A screen shot of the website can be seen below:

The visualization relates to our discussion in class about triadic closure - a property that is satisfied when A has a strong connection to both B & C, and B & C have at least a weak connection between them. In a similar sense, digg users read different articles and are more inclined to visit other articles that are linked together. The size of the nodes indicate the popularity of the article based on which how many diggers read the story. Also, certain diggers have more clout than others depending on who their friends are in the digg network. This is somewhat related to our discussion in class about PageRanking - the more reputable a hub is (the more connections it has to the most popular results), the more inclined you are to trust that hub to give you what you want. In this case, the better connected digg users are the hubs that point to stories of interest to you. The more hubs that point to a particular story become the most popular and most viewed (i.e. the largest node).

In class, we learned about Google advertising algorithm that is mainly used in Google AdWords. AdWords is Google’s advertising product and its main source of revenue. Advertisers bid on the word(s) that will trigger their aids when a user searches that word(s) on Google’s search engine. Therefore, Google not only revolutionize how people create searches on the internet but also revolutionize how people advertise. This new way of advertisement is known as ‘contextual advertising’.

Due to the great success of AdWords, Google created another ad serving program called Google AdSense. Unlike AdWords which provide revenues to Google, AdSense provide revenues for website owners. These owners signed up for the Google AdSense service where Google determined whether the site is ‘clean’ in term of the content of the website. Then AdSense will generate ads based on the content of the website.

An example of a website with advertisement:

How does Adsense work? The source of the ads comes from AdWords. Advertisers who bids on AdWords for a keyword provide ads that show up on the Google search page as well as those websites signed up for AdSense. The relationship between AdWords and AdSense are too complex to explain in a few sentences.

This block diagram show an high level diagram of the relationship between AdWords and AdSense:

Along the line of what we learned in class, the concept that the world react to what you [Google] do. This is reflected on AdSense Advertising Program where the website owners make their websites more appealing to attract Ad from Google. There are websites called MFA (Made For AdSense) which contain mostly ads from AdSense. However, currently, there are some websites owners [who maintained blogs about their hobbies, etc.] who are making money the way Google is making money, by selling slots for ads. It also benefits some advertisers who couldn’t get the slots on Google site. For example, let’s say a small company’s [that sell computer & gadgets] ad might come up on a website that has blogs on computer-enthusiasts and gadgets-lovers.

References:

Block- Diagram::www.vaughns-1-pagers.com/internet/adwords-adsense-diagram.htm

Ted Talk introducing AdSense: http://www.ted.com/index.php/talks/view/id/118

http://en.wikipedia.org/wiki/AdSense

The future of television is of course going to be digital and HD, but it is also going to be watched strictly from the computer screen or a television which now are interchangeable. Computer users have the ability to watch an episode of say “The Office” on a wide screen HDTV, stop it and click to read the news in another window at an instant. That new wave of television going digital and television being watched over the web is proving Bill Gates prediction correct.

Sites like Hulu.com are pushing television over the web to new heights. Hulu.com, a joint venture between NBC and News Corp allows a portal to free streaming television shows and movies. While being able to watch these television shows the user can view them in HD players much like the videos on abc.com. Although most of the video is ad based, they are only around 15 seconds long. This is alot better than going to sites created by individuals offering “free” content but really overing you viruses.

This is another move that pushes most television channels to put its content online and allowing the user control of which shows he or she would like to watch rather than going by the channel listing. The idea of HDTV uses the ideas of tipping point where it takes the right small amount of individuals to begin an epidemic such as NBC, CBS, and sites like Hulu. This along with the push by the government to force everyone to use digital television is creating the wave of free ad-supported television or movies via the internet.

Many aspects in class could be analyzed in this new market for examples auctions will come into place when more and more advertising bid for time slots during the streaming movies or television episodes. Game theory could also be analyzed where those players whose chose to take risks and join this new market are benefiting from it more than late comers would. Now more individuals who feel that entering the online television market is there best strategy at this point where they will benefit the most. Also much like the pay-per click idea of search engines sites like Hulu are receiving revenue from advertisers through traffic or the embedding of the clips by users onto their personal web pages which expands that advertisers potential customer base by allowing more viewing.

      Brokers connect two parties which do not have ties between them. As we covered in lecture, brokers can enjoy one’s power when they have no competition. In real life, it is easy to find brokers in many cases, ranging from brokers involved in relatively trite issues to ones involved in international issues. In my opinion, brokers are just part of the market in most of the cases, because there are competitions between them, and they do not have such powers. For example, consider a case where one student wants to sell his laptop. In this case, there could be someone who both knows this students and other student who wants to buy a laptop. He can become a broker by connecting those two students. However, in real examples, it is rare to be only one broker. Another example could be internet auction websites. Those who want to sell and buy are connected by these websites, but there is no single website; there are many website, even though specific website can be well-known than other ones.         

   However, as the article Too many brokers shows, brokers are not limited to ones who buy and sell “goods.” In the article, there are many types of brokers involved in different issues, such as visa, money laundering, real estate, and so far. Even though I never had any personal feelings toward brokers, the article says that in Korea “calling someone a broker is almost an insult.”      

      It seems that the author of this article views brokers negatively. Considering this view, it is not strange to see how the author says about the merits of brokers; “All they have is a tongue for smooth talk and all kinds of connections to exploit even the faintest acquaintance.” However, I do not agree with the author. The author mentioned about the cases which higher class was involved with brokers. However, is it easy to access to people from high class? “A tongue for smooth talk” is not the only merit brokers have and needs. Among some merits brokers have and need, connection to various networks seems like the most important feature for me.

           Even though the author only mentioned about the “tongue” a broker has, connection to various networks are more important. Consider a case where a broker has a good “tongue,” but has no connection to various networks. It is true that he would be good at compromising and persuading people, but he possibly would not even have people to persuade. In the article, there is an example of money laundering. If the broker, who I mentioned above as an example, only knows who can do the money laundering, could he success as a broker? To success, he also has to know someone who has money that needs laundering. By knowing only one party or none at all, the broker does not even have a chance to use his “tongue.” Consider another case where a broker has a normal “tongue”, but has access to various networks. Although he might not be very good at compromising and persuading, he at least knows people who need his help. Though he could not earn much profit due to his lack of skill to communicate, he could at least gain some profit.

http://joongangdaily.joins.com/article/view.asp?aid=2647839