Graphs in computer science are a way of defining relationships in the totality of elements. These are the main objects of study of graph theory.
Basic definitions
What does a graph in computer science consist of? It includes many objects called vertices or nodes, some pairs of which are connected by so-called. ribs. For example, the graph in Figure (a) consists of four nodes, labeled A, B, C, and D, of which B is connected to each of the other three vertices by edges, and C and D are also connected. Two nodes are adjacent if they are connected by an edge. The figure shows a typical way of building graphs using computer science. The circles represent the vertices, and the lines connecting each pair of them are edges.
Which graph is called non-oriented in computer science? In him, the relations between the two ends of the ribs are symmetrical. The rib simply connects them to each other. In many cases, however, asymmetric relationships need to be expressed - for example, that A points to B, but not vice versa. This purpose is served by the definition of a graph in computer science, which still consists of a set of nodes together with a set of oriented edges. Each oriented edge is a connection between the vertices, the direction of which matters. Directional graphs are depicted as shown in figure (b), their edges are represented by arrows. When it is required to emphasize that the graph is non-directional, it is called undirected.
Network Models
Graphs in computer science serve as a mathematical model of network structures. The following figure shows the structure of the Internet, then called ARPANET, in December 1970, when it had only 13 points. Nodes are computer centers, and edges connect two vertices with a direct connection between them. If you do not pay attention to the overlay map of the United States, the rest of the image is a 13-node graph, similar to the previous one. Moreover, the actual location of the peaks is not significant. It is important which nodes are connected to each other.
The use of graphs in computer science allows us to imagine how things are either physically or logically interconnected in a network structure. The 13-node ARPANET is an example of a communications network in which vertex computers or other devices can transmit messages and edges are direct lines of communication through which information can be transmitted.
Routes
Although graphs are used in many different areas, they share common features. Graph theory (computer science) includes perhaps the most important of them - the idea that things often move along the edges, sequentially moving from node to node, whether it is a passenger of several flights or information transmitted from person to person on a social network, or a user A computer that sequentially visits a number of web pages by following the links.
This idea motivates the definition of a route as a sequence of vertices connected by edges. Sometimes it becomes necessary to consider a route that contains not only nodes, but also a sequence of edges connecting them. For example, the sequence of vertices MIT, BBN, RAND, UCLA is a route in the Internet graph ARPANET. The passage of nodes and edges can be repeated. For example, SRI, STAN, UCLA, SRI, UTAH, MIT is also a route. A path in which edges do not repeat is called a chain. If the nodes are not repeated, then it is called a simple chain.
Cycles
Especially important types of graphs in computer science are loops, which represent a ring structure, such as a sequence of LINC, CASE, CARN, HARV, BBN, MIT, LINC nodes. Routes with at least three edges, in which the first and last nodes are the same and the others are different, are cyclic graphs in computer science.
Examples: SRI, STAN, UCLA, SRI cycle is the shortest, and SRI, STAN, UCLA, RAND, BBN, UTAH, SRI are much larger.
In fact, each edge of the graph ARPANET belongs to a cycle. This was done on purpose: if any of them fails, there will remain the possibility of moving from one node to another. Cycles in communication and transport systems are present to provide redundancy - they provide alternative routes along a different cycle path. In a social network, cycles are also often noticeable. When you find, for example, that your wife’s cousin’s close school friend is actually working with your brother, then this is a cycle that consists of you, your wife, her cousin, his school friend, his employee (i.e. your brother) and finally you again.
Connected graph: definition (computer science)
It is natural to ask whether it is possible to get to any other node from each node. A graph is connected if there is a route between each pair of vertices. For example, the ARPANET network is a connected graph. The same can be said of most communication and transport networks, as their goal is to direct traffic from one node to another.
On the other hand, there is no a priori reason to expect that these types of graphs in computer science are widespread. For example, in a social network, it is easy to imagine two people who are not connected.
Components
If graphs in computer science are not connected, then they naturally decompose into a set of connected fragments, groups of nodes that are isolated and not intersecting. For example, the figure shows three such parts: the first is A and B, the second is C, D and E, and the third consists of the remaining vertices.
The connected components of a graph are a subset of nodes for which:
- each vertex of a subgroup has a route to any other;
- a subset is not part of some larger set in which each node has a route to any other.
When graphs in computer science are divided into their components, this is only the initial way to describe their structure. Within this component, there may be a rich internal structure important for network interpretation. For example, a formal method for determining the importance of a node is to determine how many parts the graph will split if the node is removed.
Maximum component
There is a method for the qualitative assessment of connected components. For example, there is a worldwide social network with connections between two people if they are friends.
Is she connected? Probably not. Connectivity is a rather fragile property, and the behavior of one node (or a small set of them) can nullify it. For example, one person without any living friends will be a component consisting of a single vertex, and therefore the graph will not be connected. Or a remote tropical island, consisting of people who have no contact with the outside world, will also be a small component of the network, which confirms its incoherence.
Global network of friends
But there is one more thing. For example, a reader of a popular book has friends who have grown up in other countries, and makes up one component with them. If we take into account the parents of these friends and their friends, then all these people are also in the same component, although they have never heard of the reader, speak a different language and have never been near him. Thus, although the global friendship network is not connected, the reader will enter a component of a very large size, penetrating into all parts of the world, including people from different layers and, in fact, containing a significant part of the world's population.
The same is true for network datasets — large, complex networks often have a maximum component, which includes a significant portion of all nodes. Moreover, when a network contains a maximum component, it is almost always only one. To understand why, you should return to the example of a global friendship network and try to imagine the presence of two maximum components, each of which includes millions of people. It will take a single edge from one of the first component to the second, so that the two maximum components merge into one. Since the edge is the only one, in most cases it is unbelievable that it does not form, and, therefore, the two maximum components in real networks are never observed.
In some rare cases, when two maximum components coexisted for a long time in a real network, their combination was unexpected, dramatic, and, ultimately, had disastrous consequences.
Component merger disaster
For example, after the arrival of European researchers in the civilization of the Western Hemisphere, about a millennium ago, a global cataclysm occurred. From the point of view of the network, it looked like this: for five thousand years, the global social network probably consisted of two gigantic components - one in North and South America, and the other in Eurasia. For this reason, technology has developed independently in two components, and, even worse, human diseases have also developed, etc. When the two components finally came into contact, the technologies and diseases of one quickly and catastrophically overwhelmed the second.
American high school
The concept of maximum components is useful for discussions about networks and in much smaller sizes. An interesting example is a graph illustrating romantic relationships in an American high school over an 18-month period. The fact that it contains the maximum component is important when it comes to the spread of sexually transmitted diseases, which was the purpose of the study. The students may have had only one partner for this period of time, but, without realizing it, they were part of the maximum component and, therefore, part of many potential transmission routes. These structures reflect relationships that may have ended long ago, but they bind individuals in chains too long to become the subject of intense attention and gossip. Nevertheless, they are real: as social facts, these are invisible, but logical macrostructures arising as a product of individual mediation.
Distance and breadth-first search
In addition to information about whether the two nodes are connected by a route, graph theory in computer science also allows you to find out about its length - in transport, communications, or in the distribution of news and diseases, as well as whether it passes through several peaks or many.
To do this, you must determine the length of the route, equal to the number of steps that it contains from beginning to end, that is, the number of edges in the sequence that makes it up. For example, the route MIT, BBN, RAND, UCLA has a length of 3, and MIT, UTAH has a length of 1. Using the path length, we can talk about whether two nodes in the graph are located close to each other or far: the distance between two vertices is defined as the length the shortest way between them. For example, the distance between LINC and SRI is 3, although to verify this, make sure that there is no length of 1 or 2 between them.
Width Search Algorithm
For small graphs, the distance between two nodes is easy to calculate. But for complex, there is a need for a systematic method for determining distances.
The most natural way to do this, and therefore the most effective, is the following (using the example of a global network of friends):
- All friends are declared to be at a distance of 1.
- All friends of friends (not counting those already marked) are declared to be at a distance of 2.
- All their friends (again, not counting tagged people) are declared deleted at a distance of 3.
Continuing in this way, the search is carried out in subsequent layers, each of which is one unit farther than the previous one. Each new layer is made up of nodes that have not yet participated in the previous ones, and which enter the edge with the top of the previous layer.
This technique is called breadth-first search, as it searches the graph outward from the starting node, primarily covering the closest. In addition to providing a method for determining distance, it can serve as a useful conceptual basis for organizing the structure of a graph, as well as how to construct a graph in computer science, locating vertices based on their distance from a fixed starting point.
The breadth-first search can be applied not only to a network of friends, but also to any graph.
The world is small
If you return to the global network of friends, you can see that the argument explaining belonging to the maximum component actually says something more: not only does the reader have routes to friends that connect him with a significant proportion of the world's population, but these routes are surprisingly short .
This idea was called the “close peace phenomenon”: the world seems small when you think about the short route that connects any two people.
The theory of “six handshakes” was first experimentally investigated by Stanley Milgram and his colleagues in the 1960s. Having no data set of social networks and with a budget of $ 680, he decided to test a popular idea. To this end, he asked 296 randomly selected initiators to try sending a letter to a stockbroker who lived in a suburb of Boston. The initiators were given some personal information about the goal (including address and profession), and they had to forward a letter to a person whom they knew by name, with the same instructions, so that it would reach the goal as quickly as possible. Each letter went through the hands of a number of friends and formed a chain that closed on a stock broker outside of Boston.
Among the 64 chains that reached the goal, the average length was six, which confirmed the number named two decades earlier in the title of the play by John Gare.
Despite all the shortcomings of this study, the experiment demonstrated one of the most important aspects of our understanding of social networks. In subsequent years, a broader conclusion was drawn from it: social networks, as a rule, have very short routes between arbitrary pairs of people. And even if such indirect connections with business leaders and political leaders do not pay off on a daily basis, the existence of such short routes plays a big role in the speed of dissemination of information, diseases and other types of infection in society, as well as in the access opportunities that the social network provides to people with completely opposite qualities.