On Monday January 23rd, YouTube posted a very interesting statistic on their blog. According to the blog post, an hour's worth of video content is put on YouTube every second. They even provided an interactive animation to share the statistic in terms of satellite orbits, bamboo growth, nyans in a nyan cat, etc. YouTube is indeed growing fast.
Although we maybe used to regarding social networks to services such as Facebook, the video sharing site YouTube also has a social network in its videos. Using the videos as the vertices and the related videos links as the directed edges, a group of researchers [1] constructed a network graph for each data set from their crawler and made some interesting findings. They were able to find the small world phenomenon in the YouTube social network.
The small world phenomenon is characterized by graphs with both high clustering and small diameter. Instead of using the average diameter or the 90th percentile, the researchers used the diameter of the largest strongly connected component of each graph and found that it was about 8. This means that instead of the six degrees of separation, there is about eight degrees from one video to another. Given that the clustering coefficient of random graphs is about 0, the clustering coefficient of the YouTube graph measured to be about 0.29 is considerably high. Because of the large clustering coefficient and the small diameter, this gives you a sense of YouTube's small world.
It will be interesting to see how these numbers change in time, especially as the number of vertices in the graph grows. How many hours of video content have been added to YouTube since you started reading?
[1] Xu Cheng; Dale, C.; Jiangchuan Liu; , "Statistics and Social Network of YouTube Videos," Quality of Service, 2008. IWQoS 2008. 16th International Workshop on , vol., no., pp.229-238, 2-4 June 2008
doi: 10.1109/IWQOS.2008.32
URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=4539688&isnumber=4539656
Thursday, January 26, 2012
Lecture 6
Today we focused on the remaining two universal properties of networks -- small diameter and high clustering. Remember that, in isolation, neither small diameter or high clustering coefficient is particularly "surprising" or difficult to explain. It is only the combination that is "surprising"... and this is what is termed "small world".
We saw that one possible explanation for small world properties is a combination of local correlation with long-range random links. However, this combination only explains the existence of short paths, it doesn't explain why we can find them so easily.
To explain this second observation (and to me the more interesting observation) we saw that the long range links have to be proportional to the distance in a very precise manner. So, it is in some sense much more rare that we can find short paths with myopic algorithms than it is for the short paths to exist in the first place.
Remember though that the models we have discussed for small world graphs DO NOT have heavy-tailed degree distributions! So, we really haven't given a "natural" mechanism that explains all four of our "universal" properties, we've just given mechanisms for each individually. Can you think of how to combine our heavy-tailed degree distribution ideas with the small world ideas?
We saw that one possible explanation for small world properties is a combination of local correlation with long-range random links. However, this combination only explains the existence of short paths, it doesn't explain why we can find them so easily.
To explain this second observation (and to me the more interesting observation) we saw that the long range links have to be proportional to the distance in a very precise manner. So, it is in some sense much more rare that we can find short paths with myopic algorithms than it is for the short paths to exist in the first place.
Remember though that the models we have discussed for small world graphs DO NOT have heavy-tailed degree distributions! So, we really haven't given a "natural" mechanism that explains all four of our "universal" properties, we've just given mechanisms for each individually. Can you think of how to combine our heavy-tailed degree distribution ideas with the small world ideas?
Wednesday, January 25, 2012
Anti-Counterfeiting Trade Agreement on the rise
Last week several major online companies blacked out parts or all of their websites in response to the Stop Online Piracy Act (SOPA) and the PROTECT IP Act (PIPA) being considered by the United States Congress. The response to the blackouts was strong and several Congressmen and Senators changed their stances on the issue due to the enormous public pressure. However, at the same time that The United States is considering legislation to regulate the internet, an international treaty is set to be signed that would create international restrictions similar to the ones proposed by SOPA and PIPA.
The Anti-Counterfeiting Trade Agreement (ACTA) has been a work in progress and since 2008 and the language in the treaty was finalized in April of 2011. ACTA is much larger in scope than the US Bills because it deals with all forms of counterfeiting, not just online piracy. However, the agreement includes many of the same provisions and ideas that made SOPA and PIPA so objectionable. ACTA holds anyone who contributes to piracy responsible for that piracy. Critics have argued that websites with user generated content are now responsible for making sure that nothing illegal is posted. This is a large burden when you consider that the largest of these websites generate millions of user posts per day.
Critics are also concerned about the language that the agreement uses. The full One of their largest concerns is the following from excerpt from Article 10.
“Each Party shall further provide that its judicial authorities have the authority to
order that materials and implements, the predominant use of which has been in the
manufacture or creation of such infringing goods, be, without undue delay and without
compensation of any sort, destroyed or disposed of outside the channels of commerce in
such a manner as to minimize the risks of further infringements.”
They think that this could be used to shutdown any site with infringing material and contend it has no checks and balances on how it would be applied.
As more and more countries prepare to sign the treaty, protests are expected. Just today, Poland saw large protests in response to the announcement that their Prime Minister is expected to sign the treaty tomorrow. Poland will join the growing list of countries that have already signed the treaty, a list which as of this post includes Australia, Canada, Japan, South Korea and the United States. Many countries in the European Union are expected to sign the treaty in the coming months, whether they face the resistance seen in Poland remains to be seen.
ACTA full text: http://www.international.gc.ca/trade-agreements-accords-commerciaux/assets/pdfs/acta-crc_apr15-2011_eng.pdf
BBC Article on ACTA protests: http://www.bbc.co.uk/news/world-europe-16735219
The Power of the Internet
Never has the Internet technology industry flexed their muscles so strongly as they did last Thursday, January 19, 2012. That day, with the website blackouts against SOPA and PIPA, they demonstrated the sheer power of the Internet’s graph to affect people’s actions and decisions. In one day, 8 million people looked up who their congressman or woman was using Wikipedia’s tool (and presumably wrote to them as well). Google convinced 4.5 million people to write to their congressman or woman. Involvement on such scale would have been unheard and was impossible only ten years ago.
I think these successes are indicative of how the web graph is structured. Rather than being totally decentralized, I feel that the web graph is very dense around a few pages, like Facebook, Twitter, Wikipedia and Google. Many sites have links into these websites and they receive a massive amount of traffic. This is why the movement was so successful – the “hubs” of the graph were the ones leading the charge.
It’s quite funny to watch how the entertainment industry has reacted to these developments. These companies are staffed by people who don’t really understand the power of the Internet and social media. For example, they have launched “a television advertising campaign supporting the anti-piracy plans” (BBC). This is almost a laughable feeble move. There is no way they are going to be able to disseminate their message at the same rate or on the same scale as Reddit, Wikipedia or Facebook through a TV advertisement.
All this shows that knowing how to exploit the social and internet graph is of enormous benefit because such a graph has enormous power. It also demonstrates that the companies that control this graph have enormous power as well, perhaps more than entertainment companies that have been around for decades. The world is changing
Sources:
http://mashable.com/2012/01/18/zuckerberg-sopa-is-poorly-thought-out-law/
http://www.bbc.co.uk/news/technology-16628143
Monday, January 23, 2012
The friendship paradox: why a web crawl gives a biased sample, and "your friends have more friends than you do"
The friendship paradox is the phenomenon that on average, your friends have more friends than you do. (Or, as Satoshi Kanazawa puts it, your girlfriend is a whore.) In an undirected graph (such as a friendship network), on average, for any node u, the average degree of u’s neighbors is greater than u’s degree. That is, the average (over all nodes u) of deg(u) < the average (over all nodes u) of the average (over nodes v adjacent to u) of deg(v). The paradox was first characterized by the sociologist Scott L. Feld (
This result is superficially paradoxical, but it always holds given the (trivial) condition that not all nodes have the same degree. Intuitively, high-degree nodes have more friends, and each of those friends has 1 link to the high-degree node. Low-degree nodes have few links pointing to them. High-degree nodes are being counted more times, so any given link is more likely to point to a high-degree node. The proof is straightforward; Wikipedia gives a proof.
This idea is fairly robust to other types of graphs. The friendship paradox holds in graphs of sexual relations, even though these are approximately bipartite graphs rather than mostly random. Similarly, in directed graphs, nodes link to nodes with higher in-degree on average, and by symmetry, nodes are linked to by nodes with higher out-degree.
Suppose we try to sample part of the web graph by breadth-first search. Obviously considering the size of the network, we will terminate the crawl early, at some depth. Assuming we’ve only crawled a small part of the network, some hand-waving proves that we will have sampled a disproportionate number of pages with high in-degree. Hence the sample obtained from the crawl is biased w.r.t. in-degree distribution, and presumably other graph statistics. (This still holds if we disregard pages with (in-)degree 0.)
The friendship paradox suggests a cheap way to allocate vaccinations without having to map out the entire social graph. We want to distribute vaccines to the most socially active people, to limit disease transmission on as many links as possible. But mapping is expensive. Instead, pick some number of people uniformly at random from the entire population. Then randomly move a friend of each a few times. The resulting set of people likely have high degree in the graph, by the friendship paradox.
SHA-256 token: 54641f52bbfd085c229515c5c4c2e82d01756820dc3da125a375cc476ac7677b
Why your friends have more friends than you do, 1991).
This result is superficially paradoxical, but it always holds given the (trivial) condition that not all nodes have the same degree. Intuitively, high-degree nodes have more friends, and each of those friends has 1 link to the high-degree node. Low-degree nodes have few links pointing to them. High-degree nodes are being counted more times, so any given link is more likely to point to a high-degree node. The proof is straightforward; Wikipedia gives a proof.
This idea is fairly robust to other types of graphs. The friendship paradox holds in graphs of sexual relations, even though these are approximately bipartite graphs rather than mostly random. Similarly, in directed graphs, nodes link to nodes with higher in-degree on average, and by symmetry, nodes are linked to by nodes with higher out-degree.
Suppose we try to sample part of the web graph by breadth-first search. Obviously considering the size of the network, we will terminate the crawl early, at some depth. Assuming we’ve only crawled a small part of the network, some hand-waving proves that we will have sampled a disproportionate number of pages with high in-degree. Hence the sample obtained from the crawl is biased w.r.t. in-degree distribution, and presumably other graph statistics. (This still holds if we disregard pages with (in-)degree 0.)
The friendship paradox suggests a cheap way to allocate vaccinations without having to map out the entire social graph. We want to distribute vaccines to the most socially active people, to limit disease transmission on as many links as possible. But mapping is expensive. Instead, pick some number of people uniformly at random from the entire population. Then randomly move a friend of each a few times. The resulting set of people likely have high degree in the graph, by the friendship paradox.
SHA-256 token: 54641f52bbfd085c229515c5c4c2e82d01756820dc3da125a375cc476ac7677b
Lecture 5
Today we talked a LOT about heavy-tails...and we managed to finish it off, despite the fire alarm!
The details of what we covered could fill a whole probability course, so don't worry if you don't feel that you could prove all the results -- focus on understanding the intuition behind what I told you. (And if you want to learn more, ask me and I'll point you in the right direction.)
In my mind the key things to take away about heavy-tails are the following:
1) Know some examples of heavy-tailed distributions (Pareto, Weibull, and LogNormal)
2) Know some generic processes that create heavy-tails -- additive process (generalized CLT), extremal processes, and multiplicative processes.
3) Know how to apply these ideas to networks in order to get a heavy-tailed degree distribution. (And be sure to look at the details of the proof for Preferential attachment, since that'll be useful on the HW.)
Like I said in class, I could go on-and-on about heavy-tails... So, I probably tried to pack too much into one lecture. You'll likely need to go back and look at the notes in order to really process everything we talked about.
The details of what we covered could fill a whole probability course, so don't worry if you don't feel that you could prove all the results -- focus on understanding the intuition behind what I told you. (And if you want to learn more, ask me and I'll point you in the right direction.)
In my mind the key things to take away about heavy-tails are the following:
1) Know some examples of heavy-tailed distributions (Pareto, Weibull, and LogNormal)
2) Know some generic processes that create heavy-tails -- additive process (generalized CLT), extremal processes, and multiplicative processes.
3) Know how to apply these ideas to networks in order to get a heavy-tailed degree distribution. (And be sure to look at the details of the proof for Preferential attachment, since that'll be useful on the HW.)
Like I said in class, I could go on-and-on about heavy-tails... So, I probably tried to pack too much into one lecture. You'll likely need to go back and look at the notes in order to really process everything we talked about.
Sunday, January 22, 2012
The Building Blocks of Economic Complexity in a Global Product Space
TEDxBoston - César A. Hidalgo - Global Product Space - YouTube
Dr. Hidalgo offers another metric, specifically one of diversity, in addition to GDP to analyze the wealth of a country.
In his analysis, a capability is a resource, whether physical good or intangible skills and services. Countries vary in capabilities which lead to different products. To create certain products, the country must have the appropriate capability. Some valuable products require specific and rare capabilities. A large hold of capabilities can be then used as a indicator of wealth. Capabilities can be estimated by product output. This is done by the method of reflections (paper). When GDP is plotted against the estimated number of capabilities (8:10, video), we get a better analysis of wealth than with just GDP because capabilities adds another dimension (Fig. 1, paper). We see that despite having similar GDPs, a country with many capabilities would tend toward other obviously wealthy countries, but a country with few capabilities would tend toward other obviously poor countries.
Looking at the product space (12:12, video), we can see that different sectors are clustered showing different geopolitical tendencies (14:00, video). Also can see that progress of a country to become more wealthy; the products of a country, e.g. Malaysia (14:35, video), migrates from nodes with a small connectivity (thus small capabilities) to those with a higher connectivity (high capabilities), which is an implication of the wealth that Malaysia has acquired over the years, which is in agreement with historical records.
In conclusion, a strategy toward wealth would be to migrate from products along edges that would lead to products that had higher connectivity.
Since a small post or video cannot do justice to the research, see his paper:
"The New, New Economy"
A few years back, the internet became the new platform for economy. Allowing for faster communication and farther reach, businesses quickly grew to a global level. Nowadays, businesses compete for customers to give the most convenient online experience instead of cultivating a actual relationships with them. However, advances in technologies have forged the way for what Hixon calls “new, new economy”, the platform of which is the smartphone.
With the number of smartphone users growing in the US and across the globe, companies who reach out through smartphone apps now have a new way to access to a large network of consumers. No longer do businesses need to appeal to the comfort of doing business in without leaving home, but the convenience of doing business anywhere and anytime with their smartphones.
With the exception of gaming apps, a business cannot be run with only an app at its front. The internet economy will not die with the emergence of the smartphone economy, however, companies that wish to survive this transition need to adjust to the new platform. For example, the internet changed the banking industry by offering customers access to their accounts and information securely online to make transfers, pay bills, and even deposit checks from their personal customers. Now, customers look for banks that offer these services from any time and any place via mobile devices.
Finally, just as was necessary with the arrival of the internet, survival in the “new, new economy” will depend of the virality of the business. Basically, survival depends on how fast you can get to the top and stay there. Consider the well-known story of the movie rental service Blockbuster and how it fell to its end because its failure to transition its business to the new terrain of the internet. A business that does not want this fate in the transition to the "new, new economy" will take heed and adjust quickly.
http://www.forbes.com/sites/toddhixon/2012/01/19/going-viral-on-the-mobile-web/
With the number of smartphone users growing in the US and across the globe, companies who reach out through smartphone apps now have a new way to access to a large network of consumers. No longer do businesses need to appeal to the comfort of doing business in without leaving home, but the convenience of doing business anywhere and anytime with their smartphones.
With the exception of gaming apps, a business cannot be run with only an app at its front. The internet economy will not die with the emergence of the smartphone economy, however, companies that wish to survive this transition need to adjust to the new platform. For example, the internet changed the banking industry by offering customers access to their accounts and information securely online to make transfers, pay bills, and even deposit checks from their personal customers. Now, customers look for banks that offer these services from any time and any place via mobile devices.
Finally, just as was necessary with the arrival of the internet, survival in the “new, new economy” will depend of the virality of the business. Basically, survival depends on how fast you can get to the top and stay there. Consider the well-known story of the movie rental service Blockbuster and how it fell to its end because its failure to transition its business to the new terrain of the internet. A business that does not want this fate in the transition to the "new, new economy" will take heed and adjust quickly.
http://www.forbes.com/sites/toddhixon/2012/01/19/going-viral-on-the-mobile-web/
Talk on "Startups" Monday at 4pm
Later in the afternoon, after our class on Monday, there will be a very interesting talk by a Caltech CS alum about what it's like to join a startup. I highly recommend attending! Details are below...
Title: Skills You Should Have at a Startup
Speaker: Anthony Chong (Caltech Alum)
Date: Monday, January 23, 2012
Time: 4:00p.m.
Place: 213 Annenberg
Abstract: After leaving Caltech, I moved in with a friend from high school as the first employee at Adaptly (a startup in NYC). Rather than going for a safer future in industry or grad school, I figured a few years in a startup would provide a faster learning environment and better vehicle for doing social good. In the first year we went from three of us working out of the living room of our apartment to 30+ people working out of our offices in New York and sales office in London. I plan to address three topics:
1. What is it like to work at a startup?
2. What are useful tools Caltech grads should know/get familiar with to contribute quickly to the software development life cycle?
3. How do you get the most out of professional development at a startup?
Title: Skills You Should Have at a Startup
Speaker: Anthony Chong (Caltech Alum)
Date: Monday, January 23, 2012
Time: 4:00p.m.
Place: 213 Annenberg
Abstract: After leaving Caltech, I moved in with a friend from high school as the first employee at Adaptly (a startup in NYC). Rather than going for a safer future in industry or grad school, I figured a few years in a startup would provide a faster learning environment and better vehicle for doing social good. In the first year we went from three of us working out of the living room of our apartment to 30+ people working out of our offices in New York and sales office in London. I plan to address three topics:
1. What is it like to work at a startup?
2. What are useful tools Caltech grads should know/get familiar with to contribute quickly to the software development life cycle?
3. How do you get the most out of professional development at a startup?
Friday, January 20, 2012
Video Games and Game Theory
Can a greater knowledge of game theory provide a significant advantage in video games? One genre of video games that stands out as having a possibility of higher success with this knowledge is MMORPG’s, or Massively Multiplayer Online Role-Playing Games. The general idea behind an MMORPG is you, the player, take on a new identity in a fantasy world online. In this game players live the life of their new persona and interact with other players through this identity. The big question is whether a knowledge of game theory will affect decisions made in this virtual world?
One aspect that could be affected by knowledge of game theory is cooperation between players in small groups. In many MMORPG’s there are missions or quests which may sometimes have the option to complete them either alone or with a group. Considering that players act as they would in real life and are “intelligent rational decision-makers,”[1] if a mission can be completed alone with a high chance of success then they will choose not to cooperate with others. However, if the probability of success for working alone is low then that player will choose to work with others. When a group of players decide to work together in order to increase the success of all members, this is an example of a Non-zero sum game. If all the players can all succeed or fail together it’s called a non-zero-sum. While all players now all have a higher chance of success, the possibility of failure is still present. Many players may use this aspect of game theory without realizing this terminology. The difference between someone who knows what a non-zero sum is and someone who does not is a player with this knowledge can use it to create good odds of success but realizes that if they have too many players in the group then, although success is much higher, the payoff will be lower because it needs to be split between the group.
[1] Roger B. Myerson (1991). Game Theory: Analysis of Conflict, Harvard University Press, p.1. Chapter-preview links, pp. vii-xi
Homework 3
Homework 3 is now posted to the course website. It is due next Friday at 1:30pm. Good luck!
Of the four questions on the HW, the 1,2, and 4 you should be able to attack now. The third one is probably best done after Monday's lecture. (4 is related to what we'll do in class on Wed, but doesn't require anything that I'll teach on Wed, so you should be able to do it now.)
As always, if you have any questions about the HW, or just want to point out typos, please post them as comments on this post and then the TAs/prof will respond ASAP.
Of the four questions on the HW, the 1,2, and 4 you should be able to attack now. The third one is probably best done after Monday's lecture. (4 is related to what we'll do in class on Wed, but doesn't require anything that I'll teach on Wed, so you should be able to do it now.)
As always, if you have any questions about the HW, or just want to point out typos, please post them as comments on this post and then the TAs/prof will respond ASAP.
Thursday, January 19, 2012
Four Degrees of Facebook
“To demonstrate that people on Earth today are much closer than
ever, a member of the group suggested a test. He offered a bet that we
could name any person among earth’s one and a half billion inhabitants
and through at most five acquaintances, one of which he knew personally,
he could link to the chosen one”
-- from Frigyes Karinthy's "Chains" [1], 1929
It's quite amazing how in 1967, Stanley Milgram found evidence of the small world phenomenon---that people are connected via six degrees of separation. This was discovered in a world without Facebook, by having people passing a single postcard to someone they knew, who would then repeat the process until it got to a specific stock broker in Boston. Specifically Milgram told them,
"IF YOU DO NOT KNOW THE TARGET PERSON ON A PERSONAL BASIS, DO NOT TRY TO CONTACT HIM DIRECTLY. INSTEAD, MAIL THIS FOLDER (POSTCARDS AND ALL) TO A PERSONAL ACQUAINTANCE WHO IS MORE LIKELY THAN YOU TO KNOW THE TARGET PERSON.You may send the folder to a friend, relative or acquaintance, but it must be someone you know on a first name basis." [1]
Most of us have probably been familiar with the small world phenomenon for a while, whether through Erdos numbers, six degrees of Kevin Bacon, or simply going to Disneyland enough times, that we've been convinced it's a small world after all. But imagine what it would have been like when Milgram first published his paper. In fact Milgram said he "asked a person of intelligence how many steps he thought it would take, and he said that it would require 100 intermediate persons, or more, to move from Nebraska to Sharon.” [1]
However, what's more surprising is that Milgram isn't the first to come up with this phenomenon. As seen from the epitaph above, Karinthy speculated it in 1929 (almost forty years before Milgram), nailing the exact number of people needed (either five or six), which is very close to Milgram's result that around 5.7 people were needed to link a randomly chosen person from Nebraska to a stock broker in Boston. But it's not even clear if Karinthy believed it was possible, but his fictional character did. Perhaps that is why Karinthy's prediction was completely ignored---it was fiction, and in fact, a short story that cannot readily be found today, at least in the English language.
Today, things are different. We don't need to make fictional characters to find out how many degrees of separation are between two people, nor do we need people mailing post cards. We just need enough people to join a social networking site, and good algorithms that extract shortest paths from such a site. Facebook recently published a paper that probably gives some of the most convincing data on six degrees of separation yet, so convincing that they've changed the name to "four degrees of separation." To be more precise, using a network with around 721 million users and 69 billion links, they've found that the average number of "intermediaries" needed to get from any Facebook user to any other is 3.74. [2] This is an important result, because up until now, very few large scale analyses of degrees of separation has been conducted, however we must analyze this result more carefully.
The first thing we must note is that Facebook is not the same as the world. This experiment is fundamentally different from Milgram's on many levels. First of all, Milgram did not use any algorithm to find the shortest path between two individuals, he had them find it themselves! Almost surely (not in the mathematical sense however) people did not actually find the shortest path, however they found pretty short paths. First of all, only 22% of the participants in Milgram's experiment actually found a path from themselves to the target (by mailing postcards). What's interesting is that the average path by people who lived in Boston had 4.4 intermediaries as opposed to 5.7 intermediaries from people living in Nebraska, who may have not known anyone in Boston. This is quite fascinating, since the difference is really only one person, so maybe people who live in Nebraska are very likely to know someone in Boston. Another interesting result that Milgram found was that stock brokers in Nebraska were about as far from the target (a stock broker) as random Nebraskans. This is quite surprising, and I don't expect the result to hold today, do to the vast amount of networking among people of similar professions, especially stock brokers. But again, the most surprising thing is that people can find a very short path (perhaps only using two more people than the shortest, given the Facebook result), simply by taking a local action (i.e. people only choose who to send their post card to without knowing anything about the structure of the network besides who they know, and who they think their friends might know). The Facebook paper remarks that recent studies have been conducted to test the route through social networks (as they did in the Milgram study) but they are still quite preliminary. Any results in how effective people are in routing would be very interesting. We had some experience with this, when trying to find the shortest path between two pages on Wikipedia in the first homework. I imagine people would be much better at finding the shortest path between two pages of Wikipedia than finding the shortest social path between themselves and some celebrity, since they know a lot more about the structure of the Wikipedia network, simply by having knowledge, than they do about the structure of a social network. Indeed, if we see the shortest path between Wikipedia pages, we are likely to recognize, most if not all of the links in many cases, whereas if we see the shortest path between us and someone else, we probably have no idea who many of the middlemen are. It would be very interesting to quantify this difference.
A second observation is that Facebook friends are not the same as real friends. In fact, one of the authors of our textbook Jon Kleinberg, remarked about the recent study that, "It’s the weak ties that make the world small," [3] But he also said, "News spreads well on weak ties. Those people I met on vacation, if they send me some cool news, I might send that to my friends. If they send me something about a protest movement, I might not." Perhaps it's not right to say that Facebook simply gives us fake connections, but rather it increases our connections. We might be on a first name basis with people today, whom if we met in the 1960s, we may have met but forgotten about soon after meeting them. I speculate Facebook makes us more social, in the sense that it increases our friendship degree, even if it makes our average friendship much weaker. One final thing to note is that there is no clear notion of a "Facebook friend." I may have less friends than someone else on Facebook, not because I am less social, but because I don't add everyone I've ever seen, let alone people on forums. I don't know how much this affects the results of the study, but I imagine it affects things like degree distribution in weird ways.
Finally, while the paper's focus is on degrees of separation, they present some other fascinating results. One interesting result is that Facebook's spid, or the ratio of the variance to the mean of its distance distribution, is 0.09, which is significantly smaller than the spid of the web graph, which is larger than 1 [2]. I am not sure what to draw from this, but it suggests there is some inherent difference between the distance distribution of the two networks. Another very interesting result is the percentage of reachable pairs in different subgraphs of Facebook. In 2007 in Italy only 0.04 percent of pairs were reachable, meaning the graph consisted of a lot of isolated components! But in 2008 25.54% were reachable. Likewise in Sweden, it went from 10.23% to 93.90% between the two years [2]. This shows how suddenly the properties of a graph can change, simply by adding more nodes, somewhat reminiscent of the thresholds we saw in class. The diameters of subgraphs of Facebook are also interesting. In the United States, the diameter is 30, and in the world, the diameter is 41 [2], which is still considerably small considering you might expect some people might only have a few friends on Facebook, who also only have a few friends, and so on until they get to the outside world.
In conclusion, it is clear that we are understanding a lot more about the distance between people in social networks due to huge networks like Facebook, and advanced algorithms that can deal with such data. However, there is a lot more to be said, and probably many more results we can get from data sets like the Facebook social network. For example, it might be interesting to find the distance of people on Facebook using only "close friends," which is presumably much larger. But regardless, I envision this study is simply a precursor to many more trying to analyze how close people really are, and how well people can find each other in a network each individual knows barely anything about.
References
[1] http://www.barabasilab.com/LinkedBook/chapters/3Ch_SixDegreesofSeparation.pdf
[2] http://arxiv.org/pdf/1111.4570v3
[3] http://www.nytimes.com/2011/11/22/technology/between-you-and-me-4-74-degrees.html?_r=1
Homework submission guidelines
Here are a few reminders and tips that come to mind, based on what we're seeing from the first problem set.
List your collaborators
Remember to list the classmates you worked with for each problem.
Attach your source code
It's part of your work too! This also applies to Mathematica/Matlab codes and commands. If you used Excel, type up the relevant formulas and functions used to produce your results, graphs, etc.
Manual submission time
If you turn in a hard copy of your set, please write down the date and time of when you turned it in. This includes late sets as well.
Email submission format
This is a plead from the TAs! We get a lot of submissions by email, and we need your help to speed up our manual process of printing everything out.First of all, please save everything as a single PDF file to make sure your submissions are formatted properly (which isn't guaranteed for Word documents when opened in Linux). Source can be saved as a PDF file by the "Print to PDF" function (native, Mac/Linux or CutePDF, Windows).If you have multiple PDFs (e.g. math as well as source code), you can merge them into a single PDF file using programs like pdfsam (Windows/Mac) or Ghostscript (Windows/Mac/Linux). Just remember to look over the output file to make sure you've combined everything in the right order. :)
Source code in LaTeX
If you use LaTeX to write up your sets, it's very easy to attach the source code: use the listings package and specify the filename of the source code, and the generated PDF file will automatically copy the code over with proper syntax highlighting. More details here.
Could Facebook’s New Open Graph Feature Reduce Web Diameter Even Further?
Today Facebook released a new tool for third party developers, called Open Graph, which will allow any source (website, phone application, camera, etc…) the ability to “share” the user’s actions on their Facebook page. This quickly and easily allows users to share what they have done with their friends on Facebook by posting the new content onto their wall. This feature was being done previously by a limited number of Facebook selected websites such as Spotify for letting people know what music songs the user was listening to. Open Graph now allows for any source to link to Facebook making Facebook a possible central hub for an extremely large strongly connected internet component.
Six degrees of separation is the popular notation for how far apart two distinct nodes are from each other for any given network. For the internet, the 90th percentile estimation or effective diameter is slightly higher at something closer to 8 degrees of separation. However, with the addition of Open Graph, one can imagine that the effective diameter of the internet might decrease dramatically since each link that is shared through Open Graph on Facebook has a corresponding link back to the site from whence it came, when possible. This means that every website that uses Open Graph becomes a part of a constantly growing strongly connected component*. With the release today of a third party tool for developers to integrate Open Graph with their website, any website on the internet can now potentially connect themselves to Facebook making for the possibility, however unlikely, of a completely strongly connected internet.
So a logical question would be to ask: what benefit does Facebook have being the central hub to this large strongly connected component? The answer is quite simple. Facebook is integrating Open Graph with their Timeline feature, allowing Facebook to automatically store everything you have published. This means if you want to know what song you were listening to last week, how far you ran yesterday or even the location of where you took that picture of the cat who rode a bicycle, it will all be saved in your Facebook history which will allow Facebook to target you with better ads and cause you to visit their site more often.
*An assumption is made here that the users of Open Graph have open profiles that allow for anyone else on Facebook to see their posts. In other words, all of Facebook is connected to one another. This is not true for every specific case but is likely true for the whole as the probability of any major website with Open Graph having at least one Facebook user with an open profile is large.
https://developers.facebook.com/docs/opengraph/
Wednesday, January 18, 2012
Lecture 4
Today we finished up talking about G(n,p) and then started our discussion of heavy-tails.
With respect to G(n,p), the main point today was to give you an example of how to use concentration inequalities (e.g., Markov's and Chebychev's) to prove strong threshold results, i.e., threshold results about the probability of an event occurring rather than just about the expectation of an event. Hopefully, you followed along because you'll have to do it for yourself on HW2.
With respect to heavy-tails, we just got started. We're going to talk a lot about heavy-tails next time. This time, we really only talked about what they are, mainly through giving examples. Next time, we'll talk about where they come from. I'll try to give you a glimpse at what is really a whole advanced course in applied probability....
With respect to G(n,p), the main point today was to give you an example of how to use concentration inequalities (e.g., Markov's and Chebychev's) to prove strong threshold results, i.e., threshold results about the probability of an event occurring rather than just about the expectation of an event. Hopefully, you followed along because you'll have to do it for yourself on HW2.
With respect to heavy-tails, we just got started. We're going to talk a lot about heavy-tails next time. This time, we really only talked about what they are, mainly through giving examples. Next time, we'll talk about where they come from. I'll try to give you a glimpse at what is really a whole advanced course in applied probability....
Be polite with your crawlers!
I'm glad to see that many of you are well on your way with the crawler assignment! Some of you are producing very optimized crawlers, which is great...but be careful to be polite! If you're crawler is really optimized and you hit a particular server up with too fast a request rate you can cause some trouble...it can seem like a DoS attack. So far, this has caused some issues with UGCS and the Library!
Don't get me in too much trouble!
P.S. It's great to see so many blog posts go up in recent days. So far they have all been quite interesting, so the first round is setting a high bar for those of you later in the alphabet.
Don't get me in too much trouble!
P.S. It's great to see so many blog posts go up in recent days. So far they have all been quite interesting, so the first round is setting a high bar for those of you later in the alphabet.
A Coincidental Follow-up: How Memes Propagate Through the Internet
Just two decades ago, prior to the internet, to find out the results of a presidential debate one had to either watch the debate live, hear about it from a friend, learn the results through a TV or radio report, or read about it in the newspaper the following day. Due to the smaller number of news sources, it was easier to dispel rumors and trace back any misquotes to their sources origins. Now, however, the social media landscape allows for instant broad dissemination of information from a debate. Particularly controversial statements will find their way through the intestines of the internet even faster, as people quickly express their amazement, awe and criticism through blogging. Throughout this process of posts and re-posts, the an original quotation is bound to morph as people occasionally misquote it. Tracing the evolution of a quotation throughout the internet sheds light on the structure and inter-connectivity of news websites, blogs, and social media sites. In their 2009 paper “Meme-tracking and the Dynamic of the News Cycle”, a team at Cornell University headed by Jure Leskovec developed a method for examining the path of these “memes”.
The researchers employed a novel method to track the spread of memes throughout a set of 90 million news articles and blog posts from August to November 2008. They first identified very short phrases that remain intact as they spread. This set of distinct phrases varied heavily from day to day, and was a good indicator of memes that could be traced. They then developed algorithms that were able to extract all variants of these phrases. The algorithms involved developing phrase graphs, which are directed graphs that have phrases as nodes and directed edges from one node to another if the first phrase was a direct predecessor to the second. A primary way of determining whether to place a directed edge between two nodes is if one is an excerpt of the other. The phrase was then partitioned to create connected components with a single root node that represented the origin of the meme.
When analyzing their results, Lescovec et al. were able to make some interesting conclusions about the dynamics of spread of information. There were distinctive peaks in the number of mentions of a meme on both blog and news sites. However, the peak attention from news sources occurred around two and a half ours hours before the peak attention of that phrase from bloggers. On either side of these peaks, the volume of intensity declined exponentially. Smaller peaks also showed oscillation between blogs and news sites, as the two genres of sources played off each other in mentioning a phrase.
Now, with another election season upon us, political candidates are again in the spotlight. Their statements will be spread throughout the internet through news articles, blog posts, Facebook statuses, and Twitter updates. In the past four years, the Internet has become more connected, as these websites have grown in popularity and more of the campaign trail is captured online. What would a similar meme analysis of a political phrase look like today?
Internet Memes: A Game Theory Explanation
Rebecca Black's Friday. Nyan Cat. Caramelldansen. I can has cheezburger? How is babby formed? Demotivational Posters. The list of memes goes on and on... An interesting question to explore is how these memes propagate through the internet.
Game theory might explain the reasons behind the spread of viral content on the net. As a player on the internet, one must '[gauge] whether to adopt something new based on what others immediately surrounding them do' because there is social value in following trends. For example, when many of one's friends like Farmville, one is likely to start playing Farmville in order to fit in. Two viewpoints are discussed in the article. One is epidemic spread; content goes viral because nodes with many connections adopt the meme, exposing it to a wide group of other users, who in turn also adopt the meme. Metcalfe's law backs this explanation, stating that the value of a potential sharer is n^2, where n is the number of connections the node has. Alternatively, the article proposes game theoretic spread, which differentiates between users (nodes) with many friends (connections) and those with fewer. Those who have more friends act like 'roadblocks' and are more reluctant to adopt new content. In game theoretic spread, it is nodes with fewer connections who spread the meme more quickly because they have a lower barrier of entry. Both theories appear to have merit. Those who have more friends will feel more pressure to conform than those with fewer friends, but at the same time, upon accepting a new meme, such users will exert a more powerful influence on their neighbors due to their popularity.
While game theory may help explain the spread of certain memes, according to this infographic, the meme's initial conditions are just as vital. How is viral content selected for? Although not all memes are masterpieces, they tend to provoke a reaction out of their audience. Perhaps a video is particularly embarrassing, or an image is 'absolutely hilarious'. Either way, even amateur works can be elevated to viral content because it is something we enjoy and want to share with others. Perhaps more important than the content itself is where the meme starts. Posting on a popular site like reddit, Twitter, Facebook, or influential blogs can yield good results. As Metcalfe's law suggests, social hubs in the network that generate a lot of attention will greatly assist the adoption of a meme.
The spread of internet memes and viral content is an interesting one to investigate, as it relates to cascading behavior in networks. Personally, I think it's a pretty funny business.
Tuesday, January 17, 2012
Internet Worm Exploits Social Networks
Due to the efforts of the Facebook security team, the identity of the group that released the Koobface worm has been revealed. Unlike more “traditional” worms, which are commonly spread via email or reside in suspect websites, Koobface exploited the structure of social networks by being initiated through links on Facebook. According to The New York Times, “[t]he group cleverly harnessed the infrastructures of powerful online services – from Facebook and Twitter to Google’s search engine and Blogger – to do the heavy lifting, and may have run its enterprise with just a few computers.” Due to the high degree of traffic on these sites, Koobface was able to attract a large a number of victims. Because the web graph is known to have a giant connected component, the malicious services were made readily available, especially since these popular websites tend to be hotbeds of clustering, with high degrees that greatly facilitate the speedy and efficient traversal of the web graph.
However, Facebook hopes to similarly harness the power of the web graph against the gang of cybercriminals by releasing their personal information, who until recently have been active on vkontakte.ru (Russia’s Facebook), Twitter, and Foursquare. Perhaps, this modern attempt at ostracizing would prompt the vast online community to take action. And perhaps, enough community backlash and outrage would be able to provoke some sort of retribution, whether through legal measures or otherwise. Indeed, there have been many instances where the collective action of the online community have had an enormous impact (the voting of moot as TIME magazine’s the world’s most influential person comes readily to mind). Thus, despite Russian law enforcement’s apparent apathy of apprehending cybercriminals, justice may still be served just by simply unmasking the perpetrators and making the information readily available on the web.
Symantec estimates that cybercrime revenues are about $114 billion annually worldwide. Koobface’s earnings are much more moderate, totaling an estimated $2 million a year for the past three and a half years. However, the group has refused to exploit credit card or banking information, and their means of deploying the worm have been less “ruthless” than other groups, relying on user action to install the malicious programs rather than having it install automatically. In this sense, the worm has not been at all revolutionary; however, the exploitation of social networks as a vector for facilitating the worm’s propagation is indeed something new. Given the popularity of such sites and the ease at which information is spread through them, cyber security is something that online social networks should keep in mind.
Sources:
Blackouts in Response to SOPA
The Internet is buzzing lately with news about the Stop Online Piracy Act (SOPA), a bill introduced by Texas Representative Lamar Smith. The stated goal of SOPA is to make it easier for copyright holders and the US Justice Department to deal with copyright infringement. If passed, the U.S. Attorney General could impose sanctions on online entities like search engines, ad networks, and Internet service providers, barring them from linking to sites hosting infringing content.
Today, January 18th 2012 at 12AM EST, Wikipedia, reddit, Mozilla, and dozens of other companies blacked out their websites to protest SOPA and PIPA. Still others such as Google are mounting less drastic protests by changing their web sites. Detractors of the bill claim it is tantamount to Internet censorship and that it blatantly violates the First Amendment rights of everyone on the Internet. According to some interpretations of a recent version of the bill, the U.S. Department of Justice could shut down a site like Youtube or Vimeo, who hosts user content, because just a single user has uploaded infringing content.
If enacted, SOPA would affect many different technical aspects of the Internet. Some opponents of the bill claim that ISPs would need to perform deep packet inspection to comply with orders to block users accessing infringing content. The bill could also disrupt the Domain Name System, the Internet mechanism central to turning human-readable website names like google.com into IP addresses, which are more useful for routing traffic. Suppose the DOJ requires an ISP to block access to a site after finding out that it hosts infringing content. The ISP would then need to perform DNS filtering before passing the DNS request along, basically circumventing the process.
Later in January the House of Representatives will vote on SOPA, and the Senate will vote on a similar bill, the PROTECT IP Act. We’re a long way from seeing anything like this become law, but the implications are certainly far-reaching and worth keeping an eye on. You can read more about SOPA here, but don't look now; the site will be back up tomorrow.
-Robert Karl
Monday, January 16, 2012
Data centers in the North
In recent years the idea of utilising cold climates for the cooling of data centers has become more and more real, with Google’s opening of a data center in Hamina 2009, Finland, probably being one of the best examples.
In one of the more recent investments in the area Facebook is looking to take the concept of “cool” even further as they look to open their first European data center in Luleå, Sweden, something which the British paper the Daily Mail wrote about in an October article. In the article Facebook mentions estimates of running a self-cooling system to cool the center sufficiently for an incredible eight months of the year. Along with this the offices will be warmed up using the heat generated by the operating servers making it even more energy efficient.
Northern Europe also has incredible amounts of water sources and the new Facebook center is looking to be powered using 100% renewable energy sources, possible because of the huge amount of hydroelectricity produced in the area. Not only is this very environmentally friendly but also a cheap option for the company as the electricity costs of Northern Sweden is among the lowest throughout Europe.
In addition to the cold weather northern Europe features high-speed Internet connections at a reasonable price, and this not only in bigger urban areas as one might expect. Already in 2006 I first got the option of having a 100/100 Mbps Internet connection delivered straight into my living room via fiber optics. This being in a small Swedish city with fewer than 13000 inhabitants. According to measurements by netindex.com based on users of their services there is a clear connection between household connection speeds and northern Europe with Estonia, Lithuania, Sweden and Latvia all ranking within the top 5 countries in the world. While household speeds and company connections don’t necessarily correlate it suggests a well built infrastructure which companies too are able to utilise and as plenty of bandwidth is already available the connection price is low.
Along with this colder climate areas are often less popular places to live in and it’s more often the case than not that these places tend to have huge areas of unused land surround them. This together with few competitors means the land price is lower which makes a difference, especially considering the amount of connected land which is required for huge scale data centers. Smaller municipalities also have great gain in having companies place data centers where they are at as it generates plenty of commerce and jobs for the area. In the case of Google's data center in Finland they have more than 90 workers of which they claim most come from the local area. Because of this economical factor the Swedish government granted support in excess of 100 million SEK ($14.2 million) to further gain Facebook's interest.
All in all there are very many and good reasons for data centers to take advantage of climate and power supply possibilities as their physical location has fairly limited consequences for the users of a website or service. The biggest concern probably being a minimal increase in latency with the distance generally being further away from more densely populated areas where many users reside. I believe we are likely to see many more modern data center projects of this sort in the near future alongside continued growth in cloud computing services.
Sources:
The flip side of personalized web results
Google has recently launched a new feature in search, where they integrate the social networks, especially through Google+, into the search results. Google is thus combining knowledge from the social graph as well as the web graph, which until now primarily have been seen as segregated.
This is in itself a very interesting subject, but this initiative is however also part of a larger trend, on the web: to bring individually tailored web content to users. Facebook have long been sorting content in their news feed, Amazon and YouTube are giving personalized product/video recommendations etc. This tendency slowly changes “the web” to “you web” and “my web”.
Eli Pariser, writer of the book "The Filter Bubble", sees this tendency as a problem. See the video below (which is from before Google launched their new search improvement). He argues that if our web content gets sorted to fit the things we click on or +1 the most, we won’t get a varied picture of the world, but instead kept stuck in our on little bubble. He further criticize that most of the personalization are happening without our knowledge and without us having the possibility to switch it off.
Pariser compares the situation to when journalist began to exercise journalistic ethics, and propose that ranking algorithms should also have a sense of social responsibility and rank society important results higher, and help providing a wide information picture.
I think Pariser has a really relevant point in his concerns, and he raises some important issues. There is however more to the story than that. Sorting web content is inevitable, simply because of the amount available on the internet, and is, as you know, the backbone of Google’s success. People are already reading blogs or newspapers that fit their point of view or interest, and have been doing this for generations. So do Google, facebook etc. makes this bubble effect worse? Do they have a responsibility to act as editors?
If they choose to act as editors, we get posed with a new problem. The newspaper market is diverse with many players, each with their own interpretation of society-important content. Together they create a varied media landscape. But since these web companies are such major, almost monopolistic players, we won’t get that diversity. How do we ensure that say Google choices are “the right one”, if it’s at all possible to do so? The answers aren’t easy and mix ethics, philosophy and computer science. Maybe some in this class will help solving these issues in a few years….
-T. Bertelsen
Lunch Bunch on "Green" data centers Tuesday
I just wanted to highlight one thing that I mentioned at the beginning of class last week-- I'll be giving the lunch bunch talk tomorrow (Tuesday) 12-1 on "Energy-efficient data centers" in Annenberg 105. This is a topic that's very related to what we'll be doing later in the course, so I recommend attending. Think of it as a "bonus lecture" for the course.
Also, in general I recommend that Juniors and Seniors attend all the Lunch Bunches. They are meant to be at a "Scientific American" level so that you can get something out of them, and they'll be very useful in helping you to understand what is going on in various research areas and companies. Oh, and they have free lunch! Think of them as the followup to CS9, where now you're ready to hear more of the details.
Also, in general I recommend that Juniors and Seniors attend all the Lunch Bunches. They are meant to be at a "Scientific American" level so that you can get something out of them, and they'll be very useful in helping you to understand what is going on in various research areas and companies. Oh, and they have free lunch! Think of them as the followup to CS9, where now you're ready to hear more of the details.
Sunday, January 15, 2012
The Potential of a Good Network in Politics
2012. Four years have passed and that can only mean one thing. No, it’s not about the summer Olympics; another presidential race is upon us. Candidates hit the trails and reach out to people through television ads and debates. But in the growing world of social media, these tactics are becoming much less effective. The new arena for votes is shifting toward the Internet, toward your social network.
As David Binetti mentions in his article, the “new political battleground” lies in the connections people have to one another. Many voters, especially the younger ones, no longer receive their news and information from watching TV, which greatly lessens the impact of campaign ads. Today, many voters seek opinions online from numerous news conglomerates, popular blogs, and their own friends. The thoughts and views of certain individuals can reach a much wider audience than any single campaign ad can due to the high connectivity and small diameter of the social network.
The realization Binetti brings forth in his article is that in many areas, the individual’s vote is meaningless. You might live in a state where the opposing party heavily outnumbers your side and that party has always maintained dominance. But just because your vote might not make a difference in your area, your opinions can still have an impact. A single blogger’s post about a candidate or an issue can propagate through the network and reach hundreds of followers. Some of these followers may live in “swing states”, which historically could go to either side. One of your posts on Facebook or links to articles could easily reach a friend in one of these areas and help sway their vote. The vastness of the social network allows voters to connect and get information like never before.
For a fair number of people in this class, this will be the first presidential election you’ve voted in having just missed the cutoff in 2008. Your opinions and views can make a difference in the coming election. If you see an interesting article or have thoughts about the election, feel free to share them on Facebook or Twitter. Because of the connected network structure, these views can reach many people over a wide geographical area. Your connections and the social network you form could provide an invaluable tool that could change the course of this and future elections.
As David Binetti mentions in his article, the “new political battleground” lies in the connections people have to one another. Many voters, especially the younger ones, no longer receive their news and information from watching TV, which greatly lessens the impact of campaign ads. Today, many voters seek opinions online from numerous news conglomerates, popular blogs, and their own friends. The thoughts and views of certain individuals can reach a much wider audience than any single campaign ad can due to the high connectivity and small diameter of the social network.
The realization Binetti brings forth in his article is that in many areas, the individual’s vote is meaningless. You might live in a state where the opposing party heavily outnumbers your side and that party has always maintained dominance. But just because your vote might not make a difference in your area, your opinions can still have an impact. A single blogger’s post about a candidate or an issue can propagate through the network and reach hundreds of followers. Some of these followers may live in “swing states”, which historically could go to either side. One of your posts on Facebook or links to articles could easily reach a friend in one of these areas and help sway their vote. The vastness of the social network allows voters to connect and get information like never before.
For a fair number of people in this class, this will be the first presidential election you’ve voted in having just missed the cutoff in 2008. Your opinions and views can make a difference in the coming election. If you see an interesting article or have thoughts about the election, feel free to share them on Facebook or Twitter. Because of the connected network structure, these views can reach many people over a wide geographical area. Your connections and the social network you form could provide an invaluable tool that could change the course of this and future elections.
Friday, January 13, 2012
Homework 2
Homework 2 is now posted to the course website. It is due next Friday at 1:30pm. Good luck!
If you have any questions about the HW, or just want to point out typos, please post them as comments on this post and then the TAs/prof will respond ASAP.
Don't forget to start early!
If you have any questions about the HW, or just want to point out typos, please post them as comments on this post and then the TAs/prof will respond ASAP.
Don't forget to start early!
Wednesday, January 11, 2012
Lecture 3
Well it seems like we found a new home for lectures. The room was big enough, and we weren't kicked out halfway through!
Today we moved from studying the web graph to looking at a bunch of examples of other complex networks besides the web. My goal was to illustrate that the properties we saw in the web graph aren't special to the web -- they happen in most of these other networks too. So, they are in some sense "universal".
This motivates two natural directions, which we'll spend the next few weeks studying:
1) Trying to understand what causes these properties to emerge
2) Figuring out how to exploit these properties.
We'll to 1 and then 2, spending about 3-4 lectures on each.
We started on 1 today by exploring Erdos-Renyi random graphs. We saw that this simple model won't give us all the properties we want, but that it seems promising in terms of connectivity. We'll finish up that discussion next time, and then move on to trying to understand what causes some of the other "universal" properties to emerge.
Don't forget to come to office hours tonight & tomorrow night...and of course, don't forget that HW1 is due Friday.
Today we moved from studying the web graph to looking at a bunch of examples of other complex networks besides the web. My goal was to illustrate that the properties we saw in the web graph aren't special to the web -- they happen in most of these other networks too. So, they are in some sense "universal".
This motivates two natural directions, which we'll spend the next few weeks studying:
1) Trying to understand what causes these properties to emerge
2) Figuring out how to exploit these properties.
We'll to 1 and then 2, spending about 3-4 lectures on each.
We started on 1 today by exploring Erdos-Renyi random graphs. We saw that this simple model won't give us all the properties we want, but that it seems promising in terms of connectivity. We'll finish up that discussion next time, and then move on to trying to understand what causes some of the other "universal" properties to emerge.
Don't forget to come to office hours tonight & tomorrow night...and of course, don't forget that HW1 is due Friday.
Tuesday, January 10, 2012
New room (again): Arms 155
Okay, we have another new room for lecture. We're now in Arms 155... See you all there on Wednesday!
Monday, January 9, 2012
Lecture 2
Since I'll be busy after the lecture I'm posting this beforehand...
The notes and slides for lecture 2 are now up on the course website. The key take-aways from today's lecture are the following 4 interesting properties:
1) Connectivity: The web has one "giant" connected component and all other connected components are tiny.
2) Diameter: The distance between nodes is quite small (~6 avg. distance between noes in the SCC) and, for at least the beginning decade of the web, grow logarithmically with the size of the graph.
3) Degrees: The degree distribution is not Normal... Instead it's heavy-tailed. This means we should expect a few nodes with really "huge" degree and "lots" of nodes with small degree.
4) Clustering: The web exhibits strong "homophilly", i.e., if A is connected to B and C it is significantly more likely than random for B to be connected to C.
Over the next few lectures we'll see that these properties are "universal", and we'll try to explain why they are so common.
(By the way, I'm excited to see that someone already made their first blog post!)
The notes and slides for lecture 2 are now up on the course website. The key take-aways from today's lecture are the following 4 interesting properties:
1) Connectivity: The web has one "giant" connected component and all other connected components are tiny.
2) Diameter: The distance between nodes is quite small (~6 avg. distance between noes in the SCC) and, for at least the beginning decade of the web, grow logarithmically with the size of the graph.
3) Degrees: The degree distribution is not Normal... Instead it's heavy-tailed. This means we should expect a few nodes with really "huge" degree and "lots" of nodes with small degree.
4) Clustering: The web exhibits strong "homophilly", i.e., if A is connected to B and C it is significantly more likely than random for B to be connected to C.
Over the next few lectures we'll see that these properties are "universal", and we'll try to explain why they are so common.
(By the way, I'm excited to see that someone already made their first blog post!)
Sunday, January 8, 2012
Networking into the Past
In the heyday of social media, one can hardly click in a browser without “+1”, “share on Facebook”, and “tweet this” buttons bulging from the page. However, anything that achieves internet popularity is subject to the deplorably transient attention spans of the clicking masses. In other words, the Internet is a creature of the present. The “it” topic of the week is just that, the topic for a week, and any mentions of it later lead to nothing but cries of “repost!” and downvotes on Reddit.
But Timehop’s launch this week (mentioned in the Techcrunch article here ) and Facebook’s controversial Timeline feature together may be indicating a shift in the paradigm of internet content. People may be tired of a world in which all we do is charge forward. Sometimes we want to fondly reminisce about things in the past, and we want to do so in such a way that is socially acceptable. At the moment, commenting on a friend’s pictures from three months ago is indicative of “Facebook stalking,” but even simple changes to the UI may cause peers to be a bit more appreciative of their friends’ wanting to relive memories, and maybe even inspire them to join in. The “history writing” feature mentioned in the article is especially conducive to large discussions of past events. It invites peers to join in on the journey down memory lane instead of making the reminiscing user fly solo.
Most interestingly, Timehop and other related services could possibly introduce a new dimension to social networking. The mentioned “social media nostalgia” makes every social media user’s network so much larger. Now people can be linked to each other not just by friendships, but also by past locations and past interests, courtesy of access to their historical social content. In particular, Timehop brings up content including Facebook status updates, photos, and Twitter posts from up to a year in the past. Yes, this content always existed, but allowing to user to bring it up themselves lessens the shock from how much past personal information is stored by internet companies and makes it a little more acceptable for that information to be used by said companies in order to find connections.
Foursquare, a large content source for the precursor of Timehop, is a location tracking utility, so a new connection formed by a just-accepted friend request can be further strengthened by the link that the two both played at the same beach ultimate Frisbee tournament two months ago. The graph of social connections is becoming multi-colored; edges can be drawn for a multitude of reasons. Common past interests, common past event attendance, and common past Twittered trends are all fair game.
As the internet expands the characteristics over which it forges connections between people, more and more people will become familiar with the concept, if not the name, of “six degrees of separation,” and we will all realize that links can be found between even the most unlikely pairs of social media users.
Who knows? If we add enough colors to our graph of Internet social connections, five degrees may become the new six degrees.
Friday, January 6, 2012
Homework 1
Homework 1 is now posted to the course website. It is due next Friday at 1:30pm.
To turn in the HW, you can either drop a paper copy off at Adam's office (I will soon have a box outside my door for submissions), or by email to the homework guru (in this case Raga).
If you have any questions about the HW, or just want to point out typos, please post them as comments on this post and then the TAs/prof will respond ASAP.
Don't forget to start early!
To turn in the HW, you can either drop a paper copy off at Adam's office (I will soon have a box outside my door for submissions), or by email to the homework guru (in this case Raga).
If you have any questions about the HW, or just want to point out typos, please post them as comments on this post and then the TAs/prof will respond ASAP.
Don't forget to start early!
Probability Refresher
Don't forget to attend JKs probability refresher today at 1-2:30 in Ann 213 if you have any worries of being prepared for the course.
We will post his notes to the website afterwards, but if you have any questions about what he covers, post them as comments here.
We will post his notes to the website afterwards, but if you have any questions about what he covers, post them as comments here.
Thursday, January 5, 2012
New room: Steele 102
I have confirmed a new room: Steele102. See everyone there on Monday.
In the mean time, don't forget about the probability refresher in Annenberg 213 Friday 1-2:30.
In the mean time, don't forget about the probability refresher in Annenberg 213 Friday 1-2:30.
Lecture 1
Glad to see so many faces at the first lecture... I'm working on getting a new room still, so be sure to check back before Monday to find out where the next lecture will be.
If you still have any questions about what the course is about or about the procedural details of the course, please post them as comments here or ask me at the beginning of the next class. Also, I really recommend reading through the V. Bush and T. Berners-Lee papers that I talked about in class there are links to them at the course website.
Also, be sure to remember that JK will be giving a probability refresher on Friday at 1-2pm in Annenberg 213. If you haven't had any probability since Math 2, I highly recommend attending, as being comfortable with it will be key to the first half of the course.
If you still have any questions about what the course is about or about the procedural details of the course, please post them as comments here or ask me at the beginning of the next class. Also, I really recommend reading through the V. Bush and T. Berners-Lee papers that I talked about in class there are links to them at the course website.
Also, be sure to remember that JK will be giving a probability refresher on Friday at 1-2pm in Annenberg 213. If you haven't had any probability since Math 2, I highly recommend attending, as being comfortable with it will be key to the first half of the course.
Tuesday, January 3, 2012
Welcome to CS/EE 144!
Hi everyone!
Welcome back... hope you're ready for a challenging but (hopefully) fun term.
You'll find most of the details about the course on the course website, so be sure to check there consistently. What we'll be using this blog for a few things.
Welcome back... hope you're ready for a challenging but (hopefully) fun term.
You'll find most of the details about the course on the course website, so be sure to check there consistently. What we'll be using this blog for a few things.
- It'll be a place for announcements about the course, asking/answering questions on the homework, etc. Basically, it'll be a way to avoid broadcasting emails to the class. So, please be sure to check it regularly.
- It'll be a course blog for us to post and discuss interesting papers, news articles, and general happenings related to the course. See the course website for details about how the "blog post" assignments will work.
Thursday, March 10, 2011
Final office hours
As mentioned in class, we'll have 3 office hours to help with the final HW and project plan...
Today at 7pm (in 30min)
Monday 7-9pm
Tuesday 7-9pm
Be sure to attend so that the TAs don't get lonely!
Today at 7pm (in 30min)
Monday 7-9pm
Tuesday 7-9pm
Be sure to attend so that the TAs don't get lonely!
Wednesday, March 9, 2011
Clickmaniac final results
Well, now that the ad auction assignment is over, I've arrived at a name for the winners -- clickmaniacs.
I know I'm a little late in posting this, but here are the final results (for posterity):
Doris, Dai Wei, Wenqi: 4523 clicks, 2813 actions
Wen-Hao: 2557 clicks, 1153 actions
Emil: 2511 clicks, 1325 actions
Mihail & Nihar: 761 clicks, 382 actions
Jami & Giordon: 732 clicks, 374 actions
Zack & Ye: 360 clicks, 255 actions
Fred & Scott: 329 clicks, 142 actions
George & Matt: 274 clicks, 85 actions
Ben & Claudia: 169 clicks, 71 actions
The TAs: 108 clicks, 38 actions
Andrew: 94 clicks, 24 actions
Sasha & Alejandro: 61 clicks 74 actions
Isaac & Bo: 36 clicks, 7 actions
Great job everyone! I'm blown away at how many likes/clicks you guys were able to get in a week.
I know I'm a little late in posting this, but here are the final results (for posterity):
Doris, Dai Wei, Wenqi: 4523 clicks, 2813 actions
Wen-Hao: 2557 clicks, 1153 actions
Emil: 2511 clicks, 1325 actions
Mihail & Nihar: 761 clicks, 382 actions
Jami & Giordon: 732 clicks, 374 actions
Zack & Ye: 360 clicks, 255 actions
Fred & Scott: 329 clicks, 142 actions
George & Matt: 274 clicks, 85 actions
Ben & Claudia: 169 clicks, 71 actions
The TAs: 108 clicks, 38 actions
Andrew: 94 clicks, 24 actions
Sasha & Alejandro: 61 clicks 74 actions
Isaac & Bo: 36 clicks, 7 actions
Great job everyone! I'm blown away at how many likes/clicks you guys were able to get in a week.
Final lectures
We're into the last week, and this week we're focusing on what actually makes all the things we've talked about so far in the course possible -- Data Centers. On Monday Jeremy gave an excellent overview of the MapReduce, the simple but powerful programming paradigm used for many tasks in data centers. You'll get a lot of practice with MapReduce on the HW, so that hopefully you're comfortable with it by the end of the course. In addition to the details of programming with MapReduce, Jeremy discussed the how MapReduce is actually implemented and gave some amazing statistics about its use within Google.
That brings us to today's lecture. Today, I'll spend half the class giving an overview of the design of data centers themselves, with a focus on energy-efficiency issues. If you find yourself interested in these issues, you should definitely sign up for 146 this spring since we'll be going into a lot more detail about research in this area.
Then, the last thing we'll do is a course review, where I'll quiz you all about the "big" ideas from the course, and reward correct answers with candy... Please come so that you get a reminder of all the things we covered this term.
That brings us to today's lecture. Today, I'll spend half the class giving an overview of the design of data centers themselves, with a focus on energy-efficiency issues. If you find yourself interested in these issues, you should definitely sign up for 146 this spring since we'll be going into a lot more detail about research in this area.
Then, the last thing we'll do is a course review, where I'll quiz you all about the "big" ideas from the course, and reward correct answers with candy... Please come so that you get a reminder of all the things we covered this term.
Monday, March 7, 2011
HW 7 is out
The last Homework is now posted... As usual, ask your questions here.
This one has half about auctions (GSP) and half about MapReduce (which you'll learn in today's lecture).
This Homework and your project plan are the last things of the term. Both are due at the end of finals, but there is no reason why you can't turn them in earlier if you don't want to hang around until then!
This one has half about auctions (GSP) and half about MapReduce (which you'll learn in today's lecture).
This Homework and your project plan are the last things of the term. Both are due at the end of finals, but there is no reason why you can't turn them in earlier if you don't want to hang around until then!
Monday, February 28, 2011
Project plan
As I mentioned in class, your "final exam" will be to complete either a project plan or a course module. The details are now available on the course website.
Basically, if you're taking 145 you'll do a 5-10 page plan for the project that you'll pursue in the spring term, and if not, you'll do a new course module (lecture plus a few HW problems). If the course modules are good I may adopt them for next year!
Basically, if you're taking 145 you'll do a 5-10 page plan for the project that you'll pursue in the spring term, and if not, you'll do a new course module (lecture plus a few HW problems). If the course modules are good I may adopt them for next year!
Wednesday, February 23, 2011
Lecture 9
Today we finished up routing games and then started lecture 9 -- ad auctions. We'll be doing ad auctions for the next 2-3 classes...so we'll be covering a lot about them, but still it's only the tip of the iceberg.
Today we covered a little bit of historical perspective about them and next class we'll get into the theory. We'll start with the basics of auction theory and then move to the special case of ad auctions and ad exchanges (where we'll do a little in class experiment to give you a feel for the problem).
Note -- we will be having a make-up lecture on Friday 2/25 (this friday) at 1-2:30 in Ann 213. Please be sure to attend since we'll be covering important material.
Also, we will be having only 1 office hours this week (since the HW is not due until next friday). Raga will be covering office hours Thursday 7-9. Please stop by if you have questions about the ad auction competition or about the theory part of HW6.
Today we covered a little bit of historical perspective about them and next class we'll get into the theory. We'll start with the basics of auction theory and then move to the special case of ad auctions and ad exchanges (where we'll do a little in class experiment to give you a feel for the problem).
Note -- we will be having a make-up lecture on Friday 2/25 (this friday) at 1-2:30 in Ann 213. Please be sure to attend since we'll be covering important material.
Also, we will be having only 1 office hours this week (since the HW is not due until next friday). Raga will be covering office hours Thursday 7-9. Please stop by if you have questions about the ad auction competition or about the theory part of HW6.
Monday, February 21, 2011
Homework 6
Homework 6 is now out on the course website. Do get started on problem 4 immediately - even though the competition doesn't start till Wednesday, you need to start setting up your campaigns and thinking about your advertising strategies asap so that you have time to contact me (Raga) in case you run into difficulties, and sort things out. Good luck!
Thursday, February 17, 2011
Rankmaniac finale
We had the "final search" for rankmaniac 2011 yesterday and here are the results. I hope you had fun and learned a lot...I was certainly impressed with a lot of your ideas!
Google
1) Giordan & Jamie
2) Mihail & Nihar ***
3) Zach & Ye
4) Fred & Scott
5) Sasha & Alejandro
6) Isaac & Bo
7) TAs
8) Wen-Hao
9) Doris, Dai Wei, Wenqi
10) Claudia & Ben
11) Emil
12) Andrew
13) George & Matt
Bing
1) Fred & Scott ***
2) Doris, Dai Wei, Wenqi
3) Wen-Hao
4) Zach & Ye
5) TAs
6) Emil
7) Isaac & Bo
8) Sasha & Alejandro
9) George & Matt
10) Giordon & Jamie
11) Claudia & Ben
?? Andrew
?? Mihail & Nihar
*** means top result for "rankmaniac"
1) Giordan & Jamie
2) Mihail & Nihar ***
3) Zach & Ye
4) Fred & Scott
5) Sasha & Alejandro
6) Isaac & Bo
7) TAs
8) Wen-Hao
9) Doris, Dai Wei, Wenqi
10) Claudia & Ben
11) Emil
12) Andrew
13) George & Matt
Bing
1) Fred & Scott ***
2) Doris, Dai Wei, Wenqi
3) Wen-Hao
4) Zach & Ye
5) TAs
6) Emil
7) Isaac & Bo
8) Sasha & Alejandro
9) George & Matt
10) Giordon & Jamie
11) Claudia & Ben
?? Andrew
?? Mihail & Nihar
*** means top result for "rankmaniac"
Monday, February 14, 2011
Lecture 8
Today we started the "network economics" section of the course in earnest. Our "warmup" is the case of "load balancing games". These games are motivated by the fact that a data center / server farm is simply too big to optimally assign jobs, so instead we could consider just using a greedy heuristic of sending jobs to the best server they can go. Well, this algorithm can be viewed as a game where the players are the jobs...and we spent the lecture starting the analysis of this game.
Remember -- Wednesday is the conclusion of "rankmania". We'll have the ceremonial search at 12:30 in Ann 213. So, feel free to bring your lunch...but make sure someone from your group is there so that we can easily identify which pages belong to which group and assign grades.
Also, remember that the project proposals are due wednesday at 12:30 too, so bring them along with you.
Remember -- Wednesday is the conclusion of "rankmania". We'll have the ceremonial search at 12:30 in Ann 213. So, feel free to bring your lunch...but make sure someone from your group is there so that we can easily identify which pages belong to which group and assign grades.
Also, remember that the project proposals are due wednesday at 12:30 too, so bring them along with you.
Friday, February 11, 2011
Rankmaniac reports
The rankmaniac reports from Homework 4 were due yesterday. I found two Rankmaniac reports yesterday outside Adam's office, and none today. I hope the rest of you have turned in your reports electronically to Bose (the Guru of Homework 4). If you have not submitted your reports yet, perhaps because you forgot about the report altogether, please do so immediately. Remember, the report alone is worth 50 points. If you don't submit your reports by tonight, you may not be able to claim any credit at all for a late submission.
Tuesday, February 8, 2011
Lecture 7
Yesterday's lecture was on "cascading behavior in networks", a.k.a. epidemics over networks, a.k.a., information cascades, a.k.a., diffusion over networks, ... It goes by many names.
We looked at a few "toy" models that I hope gave you a flavor for what cascades are and how network structure (specifically clustering) affects their growth. We really only touched the tip of the iceberg however, and so there are lots of related questions that would make great project ideas on this topic. I hope to see a bunch of ideas here when you turn in your project proposals.
Remember: HWs are due on Friday this week, and so office hours are Wednesday and Thursday. I'll be having mine on Wednesday, so please come early and get started on the HW (even though it's an easy week). Otherwise I'll get lonely...
We looked at a few "toy" models that I hope gave you a flavor for what cascades are and how network structure (specifically clustering) affects their growth. We really only touched the tip of the iceberg however, and so there are lots of related questions that would make great project ideas on this topic. I hope to see a bunch of ideas here when you turn in your project proposals.
Remember: HWs are due on Friday this week, and so office hours are Wednesday and Thursday. I'll be having mine on Wednesday, so please come early and get started on the HW (even though it's an easy week). Otherwise I'll get lonely...
Tuesday, February 1, 2011
Homework 5
Homework 5 is now up on the course web page. This HW is purely to get you up to speed with game theory. If you've seen it before you may find it easy, but hopefully it will be fun.
If the problems seem hard, or use terms that you don't know, be sure to come to Bose's "Intro to Game Theory" lecture this wednesday during the normal class time. If you know all the terms in the homework and it's easy for you, there's no need to come on wednesday.
As always, post your questions about the homework as comments to this post.
If the problems seem hard, or use terms that you don't know, be sure to come to Bose's "Intro to Game Theory" lecture this wednesday during the normal class time. If you know all the terms in the homework and it's easy for you, there's no need to come on wednesday.
As always, post your questions about the homework as comments to this post.
Project ideas
In yesterday's lecture Michelle gave a great overview of a bunch of different project ideas and useful tools for you to consider when looking for your own project ideas. I'm excited to see what you all come up with!
If you're still looking for a group for the project proposals, post a comment here and I'm sure you'll find others looking.
If you're still looking for a group for the project proposals, post a comment here and I'm sure you'll find others looking.
Sunday, January 30, 2011
Homework 4 Update
Some of you had doubts regarding Q2 in HW4 for the case when a webpage does not have outgoing links. Please note that the homework has been updated with a clarification. Download the new version from the course website.
Wednesday, January 26, 2011
Homework 3 clafication
Clarification regarding Q4: Q4 mentions "We add a new central node B to the network, and connect it with every other node on the ring...". Note that the "every other node" should just read as "every node" on the ring. It does NOT mean alternate nodes. So every node on the ring is linked to B independently with probability p.
If anyone has already done with the other meaning, you do not need to redo it. Sorry for the confusion!
If anyone has already done with the other meaning, you do not need to redo it. Sorry for the confusion!
Homework 4
Homework 4 was released today and is now available on the course web page. So begins rankmaniac 2011... I look forward to seeing all the crazy things you do.
(Remember not to get me in too much trouble though!)
I will be willing to post links to peoples pages from the course website if so desired. There is a limit of 1 page per group that I will link to though.
(Remember not to get me in too much trouble though!)
I will be willing to post links to peoples pages from the course website if so desired. There is a limit of 1 page per group that I will link to though.
Lecture 6
Over Monday and Wednesday this week we made our first venture into "exploiting" network structure instead of just trying to understand it. Our example of a case where using network structure makes a huge difference is "search" -- the big idea of google back in 1998 was to use network structure to identify important pages, and feed this information into their search engine. In particular, they defined a notion called "pagerank", which we explored over the two classes. Be sure to take a look at the original papers by Brin & Page on Google...it's quite interesting to read now in the context of what google has become.
Note -- understanding pagerank and the other aspects of search engines that we discuss will be very important for you on HW4, which will be posted after class today.
Note -- understanding pagerank and the other aspects of search engines that we discuss will be very important for you on HW4, which will be posted after class today.
Thursday, January 20, 2011
Homework 3
As you know, HW3 has been handed out and is available on the website. Its due next Thursday. It seems that some of you are still unsure of some basic concepts in probability. Problem 4 of this homework heavily relies on your understanding of random variables and expectations. Please, feel absolutely free to clarify your understanding during office hours with the TAs. If you prefer, you may also contact me (Raga) personally to set up a time to meet and clarify your doubts.
As usual, ask your questions on the homework as comments to this post... Good luck!
As usual, ask your questions on the homework as comments to this post... Good luck!
Wednesday, January 19, 2011
Lecture 5
Today our focus was on explaining small world properties. Remember that, in isolation, neither small diameter or high clustering coefficient is particularly "surprising" or difficult to explain. It is only the combination that is "surprising"...
But, we saw that one possible explanation for small world properties is a combination of local correlation with long-range random links. However, this combination only explains the existence of short paths, it doesn't explain why we can find them so easily.
To explain this second observation (and to me the more interesting observation) we saw that the long range links have to be proportional to the distance in a very precise manner. So, it is in some sense much more rare that we can find short paths with myopic algorithms than it is for the short paths to exist in the first place.
Remember though that the models we have discussed for small world graphs DO NOT have heavy-tailed degree distributions! So, we really haven't given a "natural" mechanism that explains all four of our "universal" properties, we've just given mechanisms for each individually. Can you think of how to combine our heavy-tailed degree distribution ideas with the small world ideas?
But, we saw that one possible explanation for small world properties is a combination of local correlation with long-range random links. However, this combination only explains the existence of short paths, it doesn't explain why we can find them so easily.
To explain this second observation (and to me the more interesting observation) we saw that the long range links have to be proportional to the distance in a very precise manner. So, it is in some sense much more rare that we can find short paths with myopic algorithms than it is for the short paths to exist in the first place.
Remember though that the models we have discussed for small world graphs DO NOT have heavy-tailed degree distributions! So, we really haven't given a "natural" mechanism that explains all four of our "universal" properties, we've just given mechanisms for each individually. Can you think of how to combine our heavy-tailed degree distribution ideas with the small world ideas?
Wednesday, January 12, 2011
Lecture 4
Today we talked a LOT about heavy-tails.
The details of what we covered could fill a whole probability course, so don't worry if you don't feel that you could prove all the results -- focus on understanding the intuition behind what I told you. (And if you want to learn more, ask me and I'll point you in the right direction.)
In my mind the key things from today are
1) Know some examples of heavy-tailed distributions (Pareto, Weibull, and LogNormal)
2) Know some generic processes that create heavy-tails -- additive process (generalized CLT), extremal processes, and multiplicative processes.
3) Know how to apply these ideas to networks in order to get a heavy-tailed degree distribution. (We introduced Preferential attachment today, and I'll do the proof of the degree distribution next time.)
Like I said in class, I could go on-and-on about heavy-tails... So, I probably tried to pack too much into 1 lecture. You'll likely need to go back and look at the notes (which will be up soon) in order to really process everything we talked about.
The details of what we covered could fill a whole probability course, so don't worry if you don't feel that you could prove all the results -- focus on understanding the intuition behind what I told you. (And if you want to learn more, ask me and I'll point you in the right direction.)
In my mind the key things from today are
1) Know some examples of heavy-tailed distributions (Pareto, Weibull, and LogNormal)
2) Know some generic processes that create heavy-tails -- additive process (generalized CLT), extremal processes, and multiplicative processes.
3) Know how to apply these ideas to networks in order to get a heavy-tailed degree distribution. (We introduced Preferential attachment today, and I'll do the proof of the degree distribution next time.)
Like I said in class, I could go on-and-on about heavy-tails... So, I probably tried to pack too much into 1 lecture. You'll likely need to go back and look at the notes (which will be up soon) in order to really process everything we talked about.
Monday, January 10, 2011
Homework 2
I know you're all still working on HW1, but HW 2 is now available on the website. We've covered everything you need to do it at this point, so feel free to get started if you're looking for things to do! It's due a week from Thursday.
As always, ask your questions as comments to this post... Good luck!
As always, ask your questions as comments to this post... Good luck!
Lecture 3
Today I showed a bunch of examples of other complex networks besides the web and illustrated that the properties we saw in the web graph aren't special to the web -- they happen in most of these other networks too. So, they are in some sense "universal".
This motivates two natural directions:
1) Trying to understand what causes these properties to emerge
2) Figuring out how to exploit these properties.
We'll to 1 and then 2, spending about 3-4 lectures on each.
We started on 1 today by exploring Erdos-Renyi random graphs. What we saw is that through a very simple random graph model we could obtain connectivity structure (a giant component and a small diameter) that very closely mimic what we saw in the web graph and the other networks. So, in some sense, there is a very simple explanation of these properties -- they result from independent random connections.
But, the Erdos-Renyi graph does not provide an explanation for clustering or heavy-tailed degree distributions. Understanding why these occur so often will be the focus of the next two lectures.
This motivates two natural directions:
1) Trying to understand what causes these properties to emerge
2) Figuring out how to exploit these properties.
We'll to 1 and then 2, spending about 3-4 lectures on each.
We started on 1 today by exploring Erdos-Renyi random graphs. What we saw is that through a very simple random graph model we could obtain connectivity structure (a giant component and a small diameter) that very closely mimic what we saw in the web graph and the other networks. So, in some sense, there is a very simple explanation of these properties -- they result from independent random connections.
But, the Erdos-Renyi graph does not provide an explanation for clustering or heavy-tailed degree distributions. Understanding why these occur so often will be the focus of the next two lectures.
Thursday, January 6, 2011
Bonus Lecture: Probability Refresher
This is a reminder for the bonus lecture (a probability refresher) I will be giving tomorrow (Friday, Jan 7) at 1pm in Annenberg 213.
Here is the plan - we'll start by recalling the definition of a random variable and then review what discrete and continuous random variables are. Following that, we'll revisit the different types of distribution functions (probability mass function, probability density function, cumulative distribution function) and discuss some standard and well known discrete and continuous random variables (Bernoulli, binomial, geometric, Poisson, uniform, exponential, normal). Then we'll define expectation of a random variable and review some of the important properties of the expectation, with particular emphasis on linearity and its applications using indicator random variables (useful for HW1).
You don't have to attend the lecture if you are really comfortable with these concepts (and can comfortably solve Problem 2 of HW1). But if you've never really kept in touch with probability for a long time, then you'd probably benefit from the lecture.
It'll be a short lecture (about one hour). The slides are pretty verbose, and could serve as a reference later on. They will be posted on the course website after the lecture tomorrow.
Update: They are now posted on the course website.
Here is the plan - we'll start by recalling the definition of a random variable and then review what discrete and continuous random variables are. Following that, we'll revisit the different types of distribution functions (probability mass function, probability density function, cumulative distribution function) and discuss some standard and well known discrete and continuous random variables (Bernoulli, binomial, geometric, Poisson, uniform, exponential, normal). Then we'll define expectation of a random variable and review some of the important properties of the expectation, with particular emphasis on linearity and its applications using indicator random variables (useful for HW1).
You don't have to attend the lecture if you are really comfortable with these concepts (and can comfortably solve Problem 2 of HW1). But if you've never really kept in touch with probability for a long time, then you'd probably benefit from the lecture.
It'll be a short lecture (about one hour). The slides are pretty verbose, and could serve as a reference later on. They will be posted on the course website after the lecture tomorrow.
Update: They are now posted on the course website.
Wednesday, January 5, 2011
Lecture 2
The notes and slides for lecture 2 are now up.
We didn't get quite a far as I'd hoped, but we'll finish up the slides next class by looking at the structure of lots of networks other than the web.
The key take-aways from today's lecture are the following 4 interesting properties:
1) Connectivity: The web has one "giant" connected component and all other connected components are tiny.
2) Diameter: The distance between nodes is quite small (~6 avg. distance between noes in the SCC) and, for at least the beginning decade of the web, grow logarithmically with the size of the graph.
3) Degrees: The degree distribution is not Normal... Instead it's heavy-tailed. This means we should expect a few nodes with really "huge" degree and "lots" of nodes with small degree.
4) Clustering: The web exhibits strong "homophilly", i.e., if A is connected to B and C it is significantly more likely than random for B to be connected to C.
We'll see next time that these four properties are "universal"...and then we'll try to explain why they are so common.
Don't forget to attend Raga's probability refresher on Friday @ 1pm in Annenberg 213!
We didn't get quite a far as I'd hoped, but we'll finish up the slides next class by looking at the structure of lots of networks other than the web.
The key take-aways from today's lecture are the following 4 interesting properties:
1) Connectivity: The web has one "giant" connected component and all other connected components are tiny.
2) Diameter: The distance between nodes is quite small (~6 avg. distance between noes in the SCC) and, for at least the beginning decade of the web, grow logarithmically with the size of the graph.
3) Degrees: The degree distribution is not Normal... Instead it's heavy-tailed. This means we should expect a few nodes with really "huge" degree and "lots" of nodes with small degree.
4) Clustering: The web exhibits strong "homophilly", i.e., if A is connected to B and C it is significantly more likely than random for B to be connected to C.
We'll see next time that these four properties are "universal"...and then we'll try to explain why they are so common.
Don't forget to attend Raga's probability refresher on Friday @ 1pm in Annenberg 213!
Tuesday, January 4, 2011
No office hours this week
Since we don't have a HW set due until next week, and we haven't really gotten going yet, I guess we won't have office hours this week (Tue or Wed), so the first office hours will be mine on the evening of Tues 1/11 at 7-8pm in Annenberg's first floor conference room. The TAs will then have their office hours on Wed 1/12 7-9pm.
As I said in class, I really hope that most of you will come to the office hours, even if you don't have questions, and work on the HW there. Then, when you have questions you can ask them of me or the TAs (or your classmates).
As I said in class, I really hope that most of you will come to the office hours, even if you don't have questions, and work on the HW there. Then, when you have questions you can ask them of me or the TAs (or your classmates).
Monday, January 3, 2011
Homework 1
Homework 1 was passed out in class today, and is available on the course website.
Note that there is a typo in the due date on the ones handed out in class -- it is due next Thursday, Jan 13 at 1:30pm. Be sure to start early.
Also, if you're nervous about whether you know enough probability, try out the first two problems and attend Raga's Probability refresher on Friday if you have any trouble.
If you have any questions about the homework (or want to point out typos), write a comments on this post and the TAs/prof will respond ASAP.
Note that there is a typo in the due date on the ones handed out in class -- it is due next Thursday, Jan 13 at 1:30pm. Be sure to start early.
Also, if you're nervous about whether you know enough probability, try out the first two problems and attend Raga's Probability refresher on Friday if you have any trouble.
If you have any questions about the homework (or want to point out typos), write a comments on this post and the TAs/prof will respond ASAP.
Lecture 1
Glad to see so many faces at the first lecture -- I hope I didn't scare too many of you away...
If you still have any questions about what the course is about or about the procedural details of the course, please post them as comments here. Also, I really recommend reading through the handouts that I gave out in class. For those of you who didn't get a copy, there are links to them posted on the course website now.
Also, be sure to remember that Raga will be giving a probability refresher on Friday at 1-2pm in Annenberg 213. If you haven't had any probability since Math 2, I highly recommend attending.
If you still have any questions about what the course is about or about the procedural details of the course, please post them as comments here. Also, I really recommend reading through the handouts that I gave out in class. For those of you who didn't get a copy, there are links to them posted on the course website now.
Also, be sure to remember that Raga will be giving a probability refresher on Friday at 1-2pm in Annenberg 213. If you haven't had any probability since Math 2, I highly recommend attending.
Subscribe to:
Posts (Atom)