The distance from me to one of my friends is 1 (as I can reach them via one "hop" along the network), the distance from me to a friend of my friend who is not also my friend is 2, and so on.Ī graph's diameter is the maximum of the geodesic distances between node pairs, and the world encapsulated by a graph is "small" if the expected number of hops between two randomly chosen people is small in some sense. (One can consider directed and weighted generalizations as well.) The number of edges in a walk is the length of the walk. A shortest path between a pair of nodes is called a geodesic path there can be more than one such path.īetween any pair of nodes in an unweighted network, one can calculate the geodesic distance, which is given by the minimum number of edges that must be traversed to travel from the starting node to the destination node. If a graph is connected, then any node can be reached via a finite-length path starting from any other node. Nodes or edges can appear multiple times in the same walk, and the number of edges in a walk is the length of the walk. A path is a walk in which no edge is traversed more than once. A walk on a network is a sequence of alternating nodes and edges that starts with a node and ends with a node such that consecutive nodes and edges in the sequence are incident to each other ( Bollobás, 2001 Newman, 2018). Nodes that are connected to each other via an edge are adjacent when an edge is attached to a node, we say that the node and edge are incident to each other. In this article, I will use the word network as a synonym of "graph", although the term "network" is often used in a more general way. A graph consists of nodes (i.e., vertices) that are connected to each other by edges.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |