"A side effect of computing in a small world web is vulnerability to viruses or other malicious software. A computer virus may be broadly defined as a program that can replicate itself while executing instructions on infected computers, without the user's knowledge. Modelling computer viruses may lead to new methods to combat them. How can we model computer viruses loose on scale-free networks?" (Anthony Bonato, "A Course on the Web Graph", 2008)
"An open problem is to design a rigorous graph model which simulates properties of physical networks such as the various levels of the internet graph. For example, any model of the internet should take into account the technological and economic constraints at work (which are more important in this context than in W)." (Anthony Bonato, "A Course on the Web Graph", 2008)
"As any mathematician can tell you, there is more to probability than gam- bling. Indeed, applications of probability theory are now common in both graph theory and theoretical computer science." (Anthony Bonato, "A Course on the Web Graph", 2008)
"Graph theory contains a myriad of elegant proofs using probabilistic methods, especially when other techniques are not applicable. An advantage of randomized methods is their ability to prove the existence of some object without explicitly constructing it." (Anthony Bonato, "A Course on the Web Graph", 2008)
"In the web graph, each vertex acts as an independent agent, which will base its decision on how to link to the existing network on local knowledge. As a result, the neighbourhood of a new vertex will often be an imperfect copy of the neighbourhood of an existing vertex. This aspect of web page generation indicates a weakness of preferential attachment models: we assume global knowledge of all vertex degrees, a clearly unrealistic hypothesis when faced with a massive set of vertices. Both the copying models of the web graph, and the duplication model for biological networks incorporate this notion of copying in their definitions." (Anthony Bonato, "A Course on the Web Graph", 2008)
"Infinite graphs possess their own rich theory which is quite different in many aspects from the finite case. [...] we will discuss some of these aspects, then attempt to apply infinite graphs to web graph theory. The approach is new and different, but we think it has and will lead to interesting mathematics and to better insights into Wand its models. As is often the case in internet mathematics, results are Inore suggestive than definitive." (Anthony Bonato, "A Course on the Web Graph", 2008)
"Preferential attachment is one of the main paradigms used in the design of web graph models. Hence, it is natural to consider limits of on-line preferential attachment models." (Anthony Bonato, "A Course on the Web Graph", 2008)
"Regardless of the finiteness of the universe, the view of W as an infinite graph presents an interesting perspective for the mathematician. Infinite graphs are fascinating creatures whose properties are often bewildering and quite unlike finite ones." (Anthony Bonato, "A Course on the Web Graph", 2008)
"Speaking of the web graph is somewhat mis- leading, as the web is an evolving structure with pages and links appearing and disappearing continuously over time. We will overlook such concerns." (Anthony Bonato, "A Course on the Web Graph", 2008)
"The presence of power law degree distributions reflects a certain undemocratic aspect of W: while most pages have a small number of links, a few pages have a large number. This is in hindsight not surprising, since the choice of links from new pages to existing ones is determined by the users' own interests. For example, it seems plausible that popular pages attract more new links than unpopular ones." (Anthony Bonato, "A Course on the Web Graph", 2008)
"The web contains a seemingly infinite ocean of information. Traversing this ocean unaided would be difficult if not impossible. As most of us experience on a daily basis, search engines are an invaluable tool to surf the vast storehouse of information available online." (Anthony Bonato, "A Course on the Web Graph", 2008)
"The web contains many communities: sets of pages sharing a common interest or topic. However, there is no consensus for a precise definition of a community in the web graph." (Anthony Bonato, "A Course on the Web Graph", 2008).
"These networks arise naturally in many diverse disciplines (such as biology, computer science, and social science), but all share the common characteristics of being massive, sparse graphs with a power law degree distribution and small world structure. Such networks have now been coined scale-free, complex, self-organizing, or heterogeneous. Our own preferred term is self-organizing, since this is suggestive of the generative mechanisms underlying the network: over time, vertices choose their neighbour according to their own predisposition, rather than necessarily following global rules." (Anthony Bonato, "A Course on the Web Graph", 2008)
No comments:
Post a Comment