Abstract
The World Wide Web, or simply Web, is a characteristic example of a social network (Newman, 2003; Wasserman & Faust, 1994). Other examples of social networks include the food web network, scientific collaboration networks, sexual relationships networks, metabolic networks, and air transportation networks. Socials networks are usually abstracted as graphs, comprised by vertices, edges (directed or not), and in some cases, with weights on these edges. Social network theory is concerned with properties related to connectivity (degree, structure, centrality), distances (diameter, shortest paths), “resilience” (geodesic edges or vertices, articulation vertices) of these graphs, models of network growth. Social networks have been studied long before the conception of the Web. Pioneering works for the characterization of the Web as a social network and for the study of its basic properties are due to the work of Barabasi and its colleagues (Albert, Jeong & Barabasi, 1999). Later, several studies investigated other aspects like its growth (Bianconi & Barabasi, 2001; Menczer, 2004; Pennock, Flake, Lawrence, Glover, & Giles, 2002; Watts & Strogatz, 1998), its “small-world” nature in that pages can reach other pages with only a small number of links, and its scale-free nature (Adamic & Huberman, 2000; Barabasi & Albert, 1999; Barabasi & Bonabeau, 2003) (i.e., a feature implying that it is dominated by a relatively small number of Web pages that are connected to many others; these pages are called hubs and have a seemingly unlimited number of hyperlinks). Thus, the distribution of Web page linkages follows a power law in that most nodes have just a few hyperlinks and some have a tremendous number of links In that sense, the system has no “scale” (see Figure 1).
Key Terms in this Chapter
Small-World Property: A network possesses the small-world property if all vertices can be reached from the others through a small number of edges.
Clustering Coefficient: The clustering coefficient of a network is defined as the ration 3*N?/N3, where N? is the number of triangles in the network and N3 is the number of connected triples.
Social Network: A social network is a set of people or groups of people with some pattern of contacts or interactions between them. Nowadays, the meaning of the term is very broad covering also other types of networks, like technological (Web, Internet, power grid), biological (gene, metabolic, food networks), whose nodes exhibit certain interactions between them.
Betweeness Centrality Index: The betweeness centrality index of a vertex v (can be defined similarly for an edge e) is the number of shortest paths between any two vertices (different from v) which pass through v.
Random Graph Model: It is a model for an undirected graph comprised by n vertices, according to which each of the possible ½ *n*(n-1) edges is independently present with some probability p, and the number of edges connected to each vertex--the degree of the vertex--is distributed according to a binomial distribution, or a Poisson distribution in the limit of large n.
Graph Diameter: Among all shortest path distances between any two vertices of a graph, the diameter of the graph is the largest of these min distances.
Scale-Free Network: A network is characterized as scale-free if the distribution of degrees of its vertices follows a power-law for large k, like the following P(k) ~ k-?. Simply stated, some vertices of such a network are highly connected while others have few connections.