## Guido Caldarelli

Print publication date: 2007

Print ISBN-13: 9780199211517

Published to Oxford Scholarship Online: January 2010

DOI: 10.1093/acprof:oso/9780199211517.001.0001

Show Summary Details
Page of

PRINTED FROM OXFORD SCHOLARSHIP ONLINE (www.oxfordscholarship.com). (c) Copyright Oxford University Press, 2017. All Rights Reserved. Under the terms of the licence agreement, an individual user may print out a PDF of a single chapter of a monograph in OSO for personal use (for details see http://www.oxfordscholarship.com/page/privacy-policy). Subscriber: null; date: 25 February 2017

# (p.253) Appendix A. Glossary

Source:
Scale-Free Networks
Publisher:
Oxford University Press

• Adjacency matrix. A matrix A of size n × n where n is the order of the graph. The element a ij is not zero if an edge goes from i to j. The value of a ij is the weight of the edge or in a multigraph the number of multiple edges between vertices i and j. If edges have no direction the matrix is symmetric, i.e. a ij = a ji.

• Betweenness. A measure of the importance of a vertex or an edge in a graph. It is obtained by counting the number of paths that pass through a vertex (site-betweenness) or through an edge (edge-betweenness) to connect every possible pair of vertices in the graph.

• Bi-partite graph. A graph is bipartite if there is a division (partition) of the vertices V into sets V 1, V 2 such that V = V 1V 2 and the two sets are independent (no vertices in V 1 are connected each other, and no vertices in V 2 are connected each other). In other words, I can colour the vertices in red and yellow such that no link exists between vertices of the same colour.

• Centrality. Also defined as the importance of a vertex or an edge. The betweenness is a measure of centrality. Another measure of centrality is obtained by considering the average distance of one vertex (or edge) from all the others.

• Clustering. A measure of edges density for a subgraph. The larger the clustering, the larger the density of edges with respect to the rest of the graph. Often the clustering reveals the existence of a community.

• Clustering Coefficient. The clustering coefficient of a vertex is given by the number of ‘triangles’ (cycles of length 3) it belongs to in the graph divided by the maximum possible number of triangles one could draw.

• Community. A set of vertices sharing similar properties. As an example, in the WWW people sharing similar interests tend to connect to the same HTML documents and tend to link to each other. In the overwhelming majority of cases a community results in large clustering.

• (p.254)
• Connectivity. A graph is connected if a path exists between any two vertices in the graph. Sometimes it is erroneously used by some authors as equivalent to degree.

• Cycle. A closed path where the end-vertices coincide.

• Degree. The degree of a vertex is the number of its edges.

• Diameter. The maximum value of distances we can find in a graph.

• Directed Graph. a graph where edges have an orientation. Contrary to oriented graph multiple edges and loops are allowed.

• Distance. The distance of two vertices is given by the number of edges in a shortest path connecting them.

• Edge, edges. The connections between the vertices of the graph. They can be simple, multiple, oriented and weighted.

• Food web. The network composed of the species living in the same area connected by the predation relationships between them. In principle it is a directed graph where loops (cannibalism) and double edges (mutual predation) are allowed

• Forest. A set of disconnected trees

• Fractal. A self-similar geometrical figure. A geometrical structure is fractal when a portion has the same ‘shape’ than the whole. Also indicated as self-similar, that is ‘similar’ (in a mathematical sense) to itself. From the Latin fractus = broken, irregular.

• Graph. A mathematical object composed of vertices (sites) connected by edges (links).

• HTML. After ‘hypertext mark-up language’. It is a way to write and link each other different documents. Most of the WWW pages are written in this way.

• Internet. The network of computers and routers linked each other by physical connections as cables or wireless connections. Not to be confused with the World Wide Web.

• Leaf, leaves. A vertex of degree one other than the root in a tree.

• Loop. An edge connecting one vertex with itself. Sometimes it is erroneously used instead of cycle.

• Motifs. All the possible graphs of a given ‘little’ (e.g. 3, 4, 5) order. Their presence in larger networks can characterize the physical system described by the graph.

• Multigraph. A graph where it is allowed to have multiple edges.

• Network. In this book, any real system that can be completely described by a graph. In some cases the term web (World Wide Web or food web) it is used with the same meaning.

• Order. The number of vertices in a graph.

• (p.255)
• Oriented Graph. A graph where edges have an orientation and contrarily to directed graphs multiple edges and loops are not allowed.

• Path. A series of consecutive edges in a graph.

• Percolation. A model for fractal growth in statistical physics. One medium is modelled by a regular grid. Sites of this grid belong to percolation clusters with probability p. When p is zero, there is no percolation cluster, when p is one, the entire medium belongs to percolation cluster. In between there is a value p c above which a percolation cluster spans the medium. At the threshold value the cluster is fractal.

• Probability density. When the possible outcomes x of a measurement are real numbers, the probability density P(x) gives the probability to obtain a value between x and x + dx.

• Probability distribution. It is the set of the probabilities P(k) for the various outcomes k in a discrete space of events.

• River network. The graph obtained by considering the paths followed by water from rainfall on a specific area.

• Root. One special vertex in a tree (for example it can be the outlet of a river network. In this case the root is the only vertex with out-degree zero).

• Scale-invariance. A property of a fractal or self-similar object that does not change when the scale of observation is varied.

• Scaling. The behaviour of physical quantities when the size L of the system or the number of constituents N tends to infinite.

• Self-affine. An object with different scaling for different directions.

• Self-similar. An object that has the property of scale-invariance. Self-similar object have the same scaling for different directions. In this book the same as fractal.

• Simple Graph. A graph with neither multiple nor oriented edges.

• Size. The number of edges in a graph.

• Taxonomy. The classification of objects in the form of a hierarchical tree by successive steps of grouping.

• Tree. A graph without cycles. When spanning, it is a subgraph that connects all the vertices of the graph

• Vertex, vertices. The basic constituents of a graph together with the edges. Vertices represent the objects, individuals or species whose relationships are modelled through the edges. Those two sets of elements form a graph

• World Wide Web. The network of documents written mostly in HTML language, connected by hyperlinks. Not to be confused with the Internet.