As we just explained, a network consists of objects with connections between them. In mathematics a network is called a graph, and objects are called vertices (or nodes) and the connections are called edges. For example, when we represent the social network of a collection of people as a graph, the vertices are the people under consideration, while the edges list all the friendships between them. Thus, when Anne and Bob are two friends in the social network, the graph contains an “Anne” vertex and a “Bob” vertex with an edge between them.
In railroad networks, the vertices represent the stations and the edges the railways that link them. Of course, sometimes we are also interested in properties of the objects and the connections, but we refrain from discussing this generalization here.
Let us mention some other examples of networks. In the FaceBook friendship network, the vertices correspond to the FaceBook users and we draw an edge between FaceBook friends. In the collaboration network of the Internet Movie Data base, the vertices correspond to actors, and we draw an edge between two actors when they have both played in the same movie. In an internet graph , the vertices could correspond to routers, while the edges correspond to physical cables connecting different routers. In the World-Wide Web, the vertices correspond to web pages and the edges correspond to hyperlinks between them. Sometimes, data sets allow for several representations in terms of networks. For example, in the Internet Movie Data base, we could also represent the movies by the vertices and draw an edge between two movies when there is an actor acting in both movies. Different network representation might give information about different properties of data sets.
In many networks, the connections are directed and this direction is important. For example, in a road network, it is pretty important to know the direction of one-way streets!
Let us discuss some common notions from graph theory. The degree of a vertex is the number of connections it has, or, in other words, the number of edges it is in. A graph is called connected when one can move between any pair of vertices by hopping from vertices to their neighbors. The graph distance between two vertices is the minimal number of edges separating them, or the minimal number of steps a walker would need to jump from source to destination. The diameter of a connected graph is the maximal graph distance between any pair of vertices in it.
The terminology used to refer to graph notions depends on the field of study. For example, an edge is sometimes called a bond, and a vertex is sometimes called a node or site, while the degree of a vertex is sometimes called its vacancy or its connectivity. We strive to consistently use the words vertex, edge and degree throughout the NetworkPages.