🕸️On Graph Theory: On Complexity

"As with any graphic, networks are used in order to discover pertinent troups of to inform others of the groups and structures discovered. It is a good means of displaying structures, However, it ceases to be a means of discovery when the elements are numerous. The figure rapidly becomes complex, illegible and untransformable." (Jacques Bertin, "Graphics and graphic information processing", 1977)

"The more complex the network is, the more complex its pattern of interconnections, the more resilient it will be." (Fritjof Capra, "The Web of Life: A New Scientific Understanding of Living Systems", 1996)

"[…] networks are the prerequisite for describing any complex system, indicating that complexity theory must inevitably stand on the shoulders of network theory. It is tempting to step in the footsteps of some of my predecessors and predict whether and when we will tame complexity. If nothing else, such a prediction could serve as a benchmark to be disproven. Looking back at the speed with which we disentangled the networks around us after the discovery of scale-free networks, one thing is sure: Once we stumble across the right vision of complexity, it will take little to bring it to fruition. When that will happen is one of the mysteries that keeps many of us going." (Albert-László Barabási, "Linked: How Everything Is Connected to Everything Else and What It Means for Business, Science, and Everyday Life", 2002)

"At an anatomical level - the level of pure, abstract connectivity - we seem to have stumbled upon a universal pattern of complexity. Disparate networks show the same three tendencies: short chains, high clustering, and scale-free link distributions. The coincidences are eerie, and baffling to interpret." (Steven Strogatz, "Sync: The Emerging Science of Spontaneous Order", 2003)

"A first step in understanding complex systems is trying to understand patterns and regularities of interactions in a way which might make it possible to break the systems down into possible subcomponents. To do so, it is necessary to find a way of representing complex systems. […] A convenient way to represent complex systems is through graphs or networks." (Jörg Reichardt, "Structure in Complex Networks", 2009)

"For the study of the topology of the interactions of a complex system it is of central importance to have proper random null models of networks, i.e., models of how a graph arises from a random process. Such models are needed for comparison with real world data. When analyzing the structure of real world networks, the null hypothesis shall always be that the link structure is due to chance alone. This null hypothesis may only be rejected if the link structure found differs significantly from an expectation value obtained from a random model. Any deviation from the random null model must be explained by non-random processes." (Jörg Reichardt, "Structure in Complex Networks", 2009)

"Discrete Mathematics is a branch of mathematics dealing with finite or countable processes and elements. Graph Theory is an area in Discrete Mathematics which studies configurations involving a set of vertices interconnected by edges (called graphs). From humble beginnings and almost recreational type problems, Graph Theory has found its calling in the modern world of complex systems and especially of the computer. Graph Theory and its applications can be found not only in other branches of mathematics, but also in scientific disciplines such as engineering, computer science, operational research, management sciences and the life sciences." (Khee Meng Koh et al, " Graph theory: Undergraduate mathematics", 2015)

"The exploding interest in network science during the first decade of the 21st century is rooted in the discovery that despite the obvious diversity of complex systems, the structure and the evolution of the networks behind each system is driven by a common set of fundamental laws and principles. Therefore, notwithstanding the amazing differences in form, size, nature, age, and scope of real networks, most networks are driven by common organizing principles. Once we disregard the nature of the components and the precise nature of the interactions between them, the obtained networks are more similar than different from each other." (Albert-László Barabási, "Network Science", 2016)

"[...] the Game of Life, in which a few simple rules executed repeatedly can generate a surprising degree of complexity. Recall that the game treats squares, or pixels, as simply on or off (filled or blank) and the update rules are given in terms of the state of the nearest neighbours. The theory of networks is closely analogous. An electrical network, for example, consists of a collection of switches with wires connecting them. Switches can be on or off, and simple rules determine whether a given switch is flipped, according to the signals coming down the wires from the neighbouring switches. The whole network, which is easy to model on a computer, can be put in a specific starting state and then updated step by step, just like a cellular automaton. The ensuing patterns of activity depend both on the wiring diagram (the topology of the network) and the starting state. The theory of networks can be developed quite generally as a mathematical exercise: the switches are called ‘nodes’ and the wires are called ‘edges’. From very simple network rules, rich and complex activity can follow." (Paul Davies, "The Demon in the Machine: How Hidden Webs of Information Are Solving the Mystery of Life", 2019)

"Most of the complexity indeed arises from the presence of entities that appear only once or very few times, but still generate cliques within the graph. Such entities are not very informative to capture patterns and provide insights. Besides, they are possibly strongly affected by statistical variability. On the other hand, we should focus on strong correlations that are supported by larger occurrences and provide more reliable statistical results." (Aldo Marzullo et al, "Graph Machine Learning" 2nd Ed., 2025)

🕸️On Graph Theory: Connectedness

"The first attempts to consider the behavior of so-called 'random neural nets' in a systematic way have led to a series of problems concerned with relations between the 'structure' and the 'function' of such nets. The 'structure' of a random net is not a clearly defined topological manifold such as could be used to describe a circuit with explicitly given connections. In a random neural net, one does not speak of 'this' neuron synapsing on 'that' one, but rather in terms of tendencies and probabilities associated with points or regions in the net." (Anatol Rapoport, "Cycle distributions in random nets", The Bulletin of Mathematical Biophysics 10(3), 1948)

"Networks are not en route from a random to an ordered state. Neither are they at the edge of randomness and chaos. Rather, the scale-free topology is evidence of organizing principles acting at each stage of the network formation process." (Albert-László Barabási, "Linked: How Everything Is Connected to Everything Else and What It Means for Business, Science, and Everyday Life", 2002)

"In a random network the loss of a small number of nodes can cause the overall network to become incoherent - that is, to break into disconnected subnetworks. In a scale-free network, such an event usually won’t disrupt the overall network because most nodes don’t have many links. But there’s a big caveat to this general principle: if a scale-free network loses a hub, it can be disastrous, because many other nodes depend on that hub." (Thomas Homer-Dixon, "The Upside of Down: Catastrophe, Creativity, and the Renewal of Civilization", 2006)

"If a network is solely composed of neighborhood connections, information must traverse a large number of connections to get from place to place. In a small-world network, however, information can be transmitted between any two nodes using, typically, only a small number of connections. In fact, just a small percentage of random, long-distance connections is required to induce such connectivity. This type of network behavior allows the generation of 'six degrees of separation' type results, whereby any agent can connect to any other agent in the system via a path consisting of only a few intermediate nodes." (John H Miller & Scott E Page, "Complex Adaptive Systems", 2007)

"A graph enables us to visualize a relation over a set, which makes the characteristics of relations such as transitivity and symmetry easier to understand. […] Notions such as paths and cycles are key to understanding the more complex and powerful concepts of graph theory. There are many degrees of connectedness that apply to a graph; understanding these types of connectedness enables the engineer to understand the basic properties that can be defined for the graph representing some aspect of his or her system. The concepts of adjacency and reachability are the first steps to understanding the ability of an allocated architecture of a system to execute properly." (Dennis M Buede, "The Engineering Design of Systems: Models and methods", 2009)

"First, what are the 'graphs' studied in graph theory? They are not graphs of functions as studied in calculus and analytic geometry. They are (usually finite) structures consisting of vertices and edges. As in geometry, we can think of vertices as points (but they are denoted by thick dots in diagrams) and of edges as arcs connecting pairs of distinct vertices. The positions of the vertices and the shapes of the edges are irrelevant: the graph is completely specified by saying which vertices are connected by edges. A common convention is that at most one edge connects a given pair of vertices, so a graph is essentially just a pair of sets: a set of objects." (John Stillwell, "Mathematics and Its History", 2010)

"Some connected graphs are 'more connected' than others. That is, a connected graph’s vulnerability to disconnection by edge- or vertex-deletion varies. Two numerical parameters, vertex-connectivity and edge-connectivity, are useful in measuring a graph’s connectedness. Intuitively, a network’s vulnerability should be closely related also to the number of  alternative paths between each pair of nodes. There is a rich body of mathematical results concerning this relationship, many of which are variations of a classical result of Menger, and some of these extend well beyond graph theory." (Jonathan L Gross et al, "Topics in Graph Theory", 2023)

"Spanning trees capture the connectedness of a graph in the most efficient way, and they provide a foundation for a systematic analysis of the cycle structure of a graph. Mathematicians regard the algebraic structures underlying the collection of cycles and edge-cuts of agraph as beautiful in their own right. Establishing connections between linear algebra and graph theory provides some powerful analytical tools for understanding a graph’s structure." (Jonathan L Gross et al, "Topics in Graph Theory", 2023)

🕸️On Graph Theory: On Randomness

"The first attempts to consider the behavior of so-called 'random neural nets' in a systematic way have led to a series of problems concerned with relations between the 'structure' and the 'function' of such nets. The 'structure' of a random net is not a clearly defined topological manifold such as could be used to describe a circuit with explicitly given connections. In a random neural net, one does not speak of 'this' neuron synapsing on 'that' one, but rather in terms of tendencies and probabilities associated with points or regions in the net." (Anatol Rapoport, "Cycle distributions in random nets", The Bulletin of Mathematical Biophysics 10(3), 1948)

"Networks are not en route from a random to an ordered state. Neither are they at the edge of randomness and chaos. Rather, the scale-free topology is evidence of organizing principles acting at each stage of the network formation process." (Albert-László Barabási, "Linked: How Everything Is Connected to Everything Else and What It Means for Business, Science, and Everyday Life", 2002)

"Like regular networks, random ones are seductive idealizations. Theorists find them beguiling, not because of their verisimilitude, but because they're the easiest ones to analyze. [...] Random networks are small and poorly clustered; regular ones are big and highly clustered." (Steven Strogatz, "Sync: The Emerging Science of Spontaneous Order", 2003)

"In a random network the loss of a small number of nodes can cause the overall network to become incoherent - that is, to break into disconnected subnetworks. In a scale-free network, such an event usually won’t disrupt the overall network because most nodes don’t have many links. But there’s a big caveat to this general principle: if a scale-free network loses a hub, it can be disastrous, because many other nodes depend on that hub." (Thomas Homer-Dixon, "The Upside of Down: Catastrophe, Creativity, and the Renewal of Civilization", 2006)

"If a network is solely composed of neighborhood connections, information must traverse a large number of connections to get from place to place. In a small-world network, however, information can be transmitted between any two nodes using, typically, only a small number of connections. In fact, just a small percentage of random, long-distance connections is required to induce such connectivity. This type of network behavior allows the generation of 'six degrees of separation' type results, whereby any agent can connect to any other agent in the system via a path consisting of only a few intermediate nodes." (John H Miller & Scott E Page, "Complex Adaptive Systems", 2007)

"Thus, nonlinearity can be understood as the effect of a causal loop, where effects or outputs are fed back into the causes or inputs of the process. Complex systems are characterized by networks of such causal loops. In a complex, the interdependencies are such that a component A will affect a component B, but B will in general also affect A, directly or indirectly. A single feedback loop can be positive or negative. A positive feedback will amplify any variation in A, making it grow exponentially. The result is that the tiniest, microscopic difference between initial states can grow into macroscopically observable distinctions." (Carlos Gershenson, "Design and Control of Self-organizing Systems", 2007)

"For the study of the topology of the interactions of a complex system it is of central importance to have proper random null models of networks, i.e., models of how a graph arises from a random process. Such models are needed for comparison with real world data. When analyzing the structure of real world networks, the null hypothesis shall always be that the link structure is due to chance alone. This null hypothesis may only be rejected if the link structure found differs significantly from an expectation value obtained from a random model. Any deviation from the random null model must be explained by non-random processes." (Jörg Reichardt, "Structure in Complex Networks", 2009)

"Self-organizing networks suffer various types of random damage. Therefore, if the network remained static, it would soon become dysfunctional. Some networks have developed highly specific screening systems which recognize and repair random damage. On the one hand, this process requires energy, which arrives in the form of perturbations or noise. On the other hand, noise-triggered network restructuring will repeat a few steps of the original self-organization and therefore constitutes a much cheaper way of providing a continuous repair function, with the additional advantage that it is always adaptive with respect to the actual environment of the network." (Péter Csermely, "Weak Links: The Universal Key to the Stabilityof Networks and Complex Systems", 2009)

"In the telephone system a century ago, messages dispersed across the network in a pattern that mathematicians associate with randomness. But in the last decade, the flow of bits has become statistically more similar to the patterns found in self-organized systems. For one thing, the global network exhibits self-similarity, also known as a fractal pattern. We see this kind of fractal pattern in the way the jagged outline of tree branches look similar no matter whether we look at them up close or far away. Today messages disperse through the global telecommunications system in the fractal pattern of self-organization." (Kevin Kelly, "What Technology Wants", 2010)

"Random search can be more efficient than nonrandom search - something that Good and Turing had discovered at Bletchley Park. A random network, whether of neurons, computers, words, or ideas, contains solutions, waiting to be discovered, to problems that need not be explicitly defined." (George B Dyson, "Turing's Cathedral: The Origins of the Digital Universe", 2012)

"Although cascading failures may appear random and unpredictable, they follow reproducible laws that can be quantified and even predicted using the tools of network science. First, to avoid damaging cascades, we must understand the structure of the network on which the cascade propagates. Second, we must be able to model the dynamical processes taking place on these networks, like the flow of electricity. Finally, we need to uncover how the interplay between the network structure and dynamics affects the robustness of the whole system." (Albert-László Barabási, "Network Science", 2016)

"It would be wrong of me to give the impression that information flow in biology is restricted to gene regulatory networks. Unfortunately, the additional complexity of some other networks makes them even harder to model computationally, especially as the simple version of 0s and 1s (off and on) mostly won’t do. On top of that, the number of components skyrockets when it comes to more finely tuned functions like metabolism. The general point remains: biology will ‘stand out’ from random complexity in the manner of its information patterning and processing, and though complex, the software account of life will still be vastly simpler than the underlying molecular systems that support it, as it is for electronic circuits." (Paul Davies, "The Demon in the Machine: How Hidden Webs of Information Are Solving the Mystery of Life", 2019)

🕸️On Graph Theory: On Structure (-1999)

"The first attempts to consider the behavior of so-called 'random neural nets' in a systematic way have led to a series of problems concerned with relations between the 'structure' and the 'function' of such nets. The 'structure' of a random net is not a clearly defined topological manifold such as could be used to describe a circuit with explicitly given connections. In a random neural net, one does not speak of 'this' neuron synapsing on 'that' one, but rather in terms of tendencies and probabilities associated with points or regions in the net." (Anatol Rapoport, "Cycle distributions in random nets", The Bulletin of Mathematical Biophysics 10(3), 1948)

"[…] semantic nets [are defined] as graphical analogues of data structures representing 'facts' in a computer system for understanding natural language." (Lenhart K Schubert," "Extending the Expressive Power of Semantic Networks", Artificial Intelligence 7, 1976)

"The concepts a person uses are represented as points, and the causal links between these concepts are represented as arrows between these points. This gives a pictorial representation of the causal assertions of a person as a graph of points and arrows. This kind of representation of assertions as a graph will be called a cognitive map. The policy alternatives, all of the various causes and effects, the goals, and the ultimate utility of the decision maker can all be thought of as concept variables, and represented as points in the cognitive map. The real power of this approach ap pears when a cognitive map is pictured in graph form; it is then relatively easy to see how each of the concepts and causal relation ships relate to each other, and to see the overall structure of the whole set of portrayed assertions." (Robert Axelrod, "The Cognitive Mapping Approach to Decision Making" [in "Structure of Decision: The Cognitive Maps of Political Elites"], 1976)

"A semantic network or net represents knowledge as a net-like graph. An idea, event, situation or object almost always has a composite structure; this is represented in a semantic network by a corresponding structure of nodes (drawn as circles or boxes) representing conceptual units, and directed links (drawn as arrows between the nodes) representing the relations between the units. […] An abstract (graph-theoretic) network can be diagrammed, defined mathematically, programmed in a computer, or hard-wired electronically. It becomes semantic when you assign a meaning to each node and link. Unlike specialized networks and diagrams, semantic networks aim to represent any kind of knowledge which can be described in natural language. A semantic network system includes not only the explicitly stored net structure but also methods for automatically deriving from that a much larger structure or body of implied knowledge." (Fritz Lehman, "Semantic Networks",  Computers & Mathematics with Applications Vol. 23 (2-5), 1992)

"The essential idea of semantic networks is that the graph-theoretic structure of relations and. abstractions can be used for inference as well as understanding. […] A semantic network is a discrete structure as is any linguistic description. Representation of the continuous 'outside world' with such a structure is necessarily incomplete, and requires decisions as to which information is kept and which is lost." (Fritz Lehman, "Semantic Networks",  Computers & Mathematics with Applications Vol. 23 (2-5), 1992)

"There is a multilayering of global networks in the key strategic activities that structure and destructure the planet. When these multilayered networks overlap in some node, when there is a node that belongs to different networks, two major consequences follow. First, economies of synergy between these different networks take place in that node: between financial markets and media businesses; or between academic research and technology development and innovation; between politics and media." (Manuel Castells, "The Rise of the Network Society", 1996)

"Graphs are one of the unifying themes of computer science - an abstract representation that describes the organization of transportation systems, human interactions, and telecommunication networks. That so many different structures can be modeled using a single formalism is a source of great power to the educated programmer." (Steven S Skiena, "The Algorithm Design Manual", 1997)

"Neural networks conserve the complexity of the systems they model because they have complex structures themselves. Neural networks encode information about their environment in a distributed form. […] Neural networks have the capacity to self-organise their internal structure." (Paul Cilliers, "Complexity and Postmodernism: Understanding Complex Systems", 1998)

"The internal structure of a connectionist network develops through a process of self-organisation, whereas rule-based systems have to search through pre-programmed options that define the structure largely in an a priori fashion. In this sense, learning is an implicit characteristic of neural networks. In rule-based systems, learning can only take place through explicitly formulated procedures." (Paul Cilliers, "Complexity and Postmodernism: Understanding Complex Systems", 1998) 

🕸️On Graph Theory: On Structure (2000-2009)

"Average path length reflects the global structure; it depends on the way the entire network is connected, and cannot be inferred from any local measurement. Clustering reflects the local structure; it depends only on the interconnectedness of a typical neighborhood, the inbreeding among nodes tied to a common center. Roughly speaking, path length measures how big the network is. Clustering measures how incestuous it is." (Steven Strogatz, "Sync: The Emerging Science of Spontaneous Order", 2003)

"Nodes and connectors comprise the structure of a network. In contrast, an ecology is a living organism. It influences the formation of the network itself." (George Siemens, "Knowing Knowledge", 2006)

"For the study of the topology of the interactions of a complex system it is of central importance to have proper random null models of networks, i.e., models of how a graph arises from a random process. Such models are needed for comparison with real world data. When analyzing the structure of real world networks, the null hypothesis shall always be that the link structure is due to chance alone. This null hypothesis may only be rejected if the link structure found differs significantly from an expectation value obtained from a random model. Any deviation from the random null model must be explained by non-random processes." (Jörg Reichardt, "Structure in Complex Networks", 2009)

"Self-organizing networks suffer various types of random damage. Therefore, if the network remained static, it would soon become dysfunctional. Some networks have developed highly specific screening systems which recognize and repair random damage. On the one hand, this process requires energy, which arrives in the form of perturbations or noise. On the other hand, noise-triggered network restructuring will repeat a few steps of the original self-organization and therefore constitutes a much cheaper way of providing a continuous repair function, with the additional advantage that it is always adaptive with respect to the actual environment of the network." (Péter Csermely, "Weak Links: The Universal Key to the Stabilityof Networks and Complex Systems", 2009) 

"To understand, how noise is related to scale-freeness, we have to do some mathematics again. Noise is usually characterized by a mathematical trick. The seemingly random fluctuation of the signal is regarded as a sum of sinusoidal waves. The components of the million waves giving the final noise structure are characterized by their frequency. To describe noise, we plot the contribution (called spectral density) of the various waves we use to model the noise as a function of their frequency. This transformation is called a Fourier transformation [...]" (Péter Csermely, "Weak Links: The Universal Key to the Stabilityof Networks and Complex Systems", 2009)

🕸️On Graph Theory: On Structure (2010-2019)

"As it turns out, complex networks are everywhere. Or, to be more precise, it turns out that if we model real-world situations in terms of networks, we often discover new things. What is striking, is that many real-world net- works look alike: the structure of the Internet resembles the organization of our brain, but also the organization of online social communities. Where these similarities come from is still a mystery, just as it is often very difficult to understand how certain networks were actually structured." (Maarten van Steen, "Graph Theory and Complex Networks: An Introduction", 2010)

"First, what are the 'graphs' studied in graph theory? They are not graphs of functions as studied in calculus and analytic geometry. They are (usually finite) structures consisting of vertices and edges. As in geometry, we can think of vertices as points (but they are denoted by thick dots in diagrams) and of edges as arcs connecting pairs of distinct vertices. The positions of the vertices and the shapes of the edges are irrelevant: the graph is completely specified by saying which vertices are connected by edges. A common convention is that at most one edge connects a given pair of vertices, so a graph is essentially just a pair of sets: a set of objects." (John Stillwell, "Mathematics and Its History", 2010)

"[...] the contexts in which a social network is embedded will generally have significant effects on its structure. Each individual in a social network has a distinctive set of personal characteristics, and similarities and compatibilities between two people’s characteristics can strongly influence whether a link forms between them. Each individual also engages in a set of behaviors and activities that can shape the formation of links within the network. These considerations suggest what we mean by a network’s surrounding contexts: factors that exist outside the nodes and edges of a networks, but which nonetheless affect how the network’s structure evolves." (David Easley & Jon Kleinberg, "Networks, Crowds, and Markets: Reasoning about a Highly Connected World", 2010)

"When people talk about the 'connectedness' of a complex system, in general they are really talking about two related issues. One is connectedness at the level of structure – who is linked to whom – and the other is connectedness at the level of behavior – the fact that each individual’s actions have implicit consequences for the outcomes of everyone in the system."(David Easley & Jon Kleinberg, "Networks, Crowds, and Markets: Reasoning about a Highly Connected World", 2010)

"Cybernetics is the study of systems which can be mapped using loops (or more complicated looping structures) in the network defining the flow of information. Systems of automatic control will of necessity use at least one loop of information flow providing feedback." (Alan Scrivener, "A Curriculum for Cybernetics and Systems Theory", 2012)

"All living systems are networks of smaller components, and the web of life as a whole is a multilayered structure of living systems nesting within other living systems - networks within networks." (Fritjof Capra, "The Systems View of Life: A Unifying Vision", 2014)

"The great strength of node–link layouts is that for sufficiently small networks they are extremely intuitive for supporting many ofthe abstract tasks that pertain to network data. They particularly shine for tasks that rely on understanding the topological structure of the network, such as path tracing and searching local topological neighborhoods a small number of hops from a target node, and can also be very effective for tasks such as general overview or finding similar substructures. The effectiveness of the general idiom varies considerably depending on the specific visual encoding idiom used [...]" (Tamara Munzner, "Visualization Analysis and Design", 2014)

"Although cascading failures may appear random and unpredictable, they follow reproducible laws that can be quantified and even predicted using the tools of network science. First, to avoid damaging cascades, we must understand the structure of the network on which the cascade propagates. Second, we must be able to model the dynamical processes taking place on these networks, like the flow of electricity. Finally, we need to uncover how the interplay between the network structure and dynamics affects the robustness of the whole system." (Albert-László Barabási, "Network Science", 2016)

🕸️On Graph Theory: On Structure (2020-2029)

"Exponentially growing systems are prevalent in nature, spanning all scales from biochemical reaction networks in single cells to food webs of ecosystems. How exponential growth emerges in nonlinear systems is mathematically unclear. […] The emergence of exponential growth from a multivariable nonlinear network is not mathematically intuitive. This indicates that the network structure and the flux functions of the modeled system must be subjected to constraints to result in long-term exponential dynamics." (Wei-Hsiang Lin et al, "Origin of exponential growth in nonlinear reaction networks", PNAS 117 (45), 2020

"A graph is a simple and quite old mathematical concept: a data structure consisting of a set of vertices (or nodes/points) and edges (or relationships/lines) that can be used to model relationships among a collection of objects." (Alessandro Negro, "Graph-Powered Machine Learning", 2021)

"Graphs are useful for representing how things are either physically or logically linked in simple or complex structures. A graph in which we assign names and meanings to the edges and vertices becomes what is known as a network. In these cases, a graph is the mathematical model for describing a network, whereas a network is a set of relations between objects, which could include people, organizations, nations, items found in a Google search, brain cells, or electrical transformers." (Alessandro Negro, "Graph-Powered Machine Learning", 2021)

"In many areas of machine learning, graphs are used to model local relationships between data elements and to build global structures from local information. Building graphs is sometimes necessary for dealing with problems arising from applications in machine learning or data mining, and at other times, it's helpful for managing data. It's important to note that the transformation from the original data to a graph data representation can always be performed in a lossless manner. The opposite is not always true." (Alessandro Negro, "Graph-Powered Machine Learning", 2021)

"Spanning trees capture the connectedness of a graph in the most efficient way, and they provide a foundation for a systematic analysis of the cycle structure of a graph. Mathematicians regard the algebraic structures underlying the collection of cycles and edge-cuts of agraph as beautiful in their own right. Establishing connections between linear algebra and graph theory provides some powerful analytical tools for understanding a graph’s structure." (Jonathan L Gross et al, "Topics in Graph Theory", 2023)

"A small-world network is characterized by a high clustering coefficient and a short average path length, meaning that most nodes can be reached from any other node through a small number of intermediate connections. This structure often mirrors real-world social networks, where individuals are typically connected through a few mutual acquaintances, allowing for rapid information dissemination." (Aldo Marzullo et al, "Graph Machine Learning" 2nd Ed., 2025)

"Assortativity is used to quantify the tendency of nodes being connected to similar nodes, which can impact the network’s ability to withstand failures or 'attacks'. High assortativity indicates that nodes of similar degrees are more likely to be connected, leading to a resilient structure where the failure of some nodes does not significantly disrupt overall connectivity. Conversely, networks with low assortativity tend to have nodes connecting with dissimilar degrees, making them more vulnerable to targeted attacks on high-degree nodes [...]" (Aldo Marzullo et al, "Graph Machine Learning" 2nd Ed., 2025)

"The concept of temporal graphs is useful in all the real-world problems that can be represented as a graph, where the nodes and edges of the graph may change over time. For example, temporal graphs are extensively applied in modeling social networks. By capturing the evolving relationships between individuals, temporal graphs enable a more accurate representation of social dynamics. This is particularly useful for predicting changes in friendships, community structures, and the information diffusion over time." (Aldo Marzullo et al, "Graph Machine Learning" 2nd Ed., 2025)

🕸️On Graph Theory: On Networks (2020-2029)

"Graphs are useful for representing how things are either physically or logically linked in simple or complex structures. A graph in which we assign names and meanings to the edges and vertices becomes what is known as a network. In these cases, a graph is the mathematical model for describing a network, whereas a network is a set of relations between objects, which could include people, organizations, nations, items found in a Google search, brain cells, or electrical transformers." (Alessandro Negro, "Graph-Powered Machine Learning", 2021)

"Graphs, with multiple node types and different types of relationships, are far from being a Euclidean space. This task is where graph neural networks (GNNs) comes in. GNNs are deep learning-based methods that operate on a graph domain to perform complex tasks such as node classification (the bot example), link prediction (the disease example), and so on. Due to its convincing performance, GNN has become a widely applied graph analysis method." (Alessandro Negro, "Graph-Powered Machine Learning", 2021)

"Networks or network graphs show relationships between things using nodes and links. Nodes are similar to the points on a scatterplot - they show one data point each. Links are the lines or arrows that show how the nodes connect or relate to each other." (Nancy Organ, "Data Visualization for People of All Ages", 2024)

"Tree maps show networks by arranging rectangular branches and leaf nodes into a big block. Each branch in a tree map is packed with leaf nodes of the same color. Sometimes, the leaf nodes are in different sizes to show different amounts." (Nancy Organ, "Data Visualization for People of All Ages", 2024)

"[...] a graph is a mathematical model that is used for describing relationships between entities. However, each complex network presents intrinsic properties. Such properties can be measured by particular metrics, and each measure may characterize one or several local and global aspects of the graph." (Aldo Marzullo et al, "Graph Machine Learning" 2nd Ed., 2025)

"A small-world network is characterized by a high clustering coefficient and a short average path length, meaning that most nodes can be reached from any other node through a small number of intermediate connections. This structure often mirrors real-world social networks, where individuals are typically connected through a few mutual acquaintances, allowing for rapid information dissemination." (Aldo Marzullo et al, "Graph Machine Learning" 2nd Ed., 2025)

"Although creating simple subgraphs and merging them is a way to generate new graphs of increasing complexity, networks may also be generated by means of probabilistic models   and/or generative models that let a graph grow by itself. Such graphs usually share   interesting properties with real networks and have long been used to create benchmarks and synthetic graphs, especially in times when the amount of data available was not as overwhelming as today." (Aldo Marzullo et al, "Graph Machine Learning" 2nd Ed., 2025)

"Assortativity is used to quantify the tendency of nodes being connected to similar nodes, which can impact the network’s ability to withstand failures or 'attacks'. High assortativity indicates that nodes of similar degrees are more likely to be connected, leading to a resilient structure where the failure of some nodes does not significantly disrupt overall connectivity. Conversely, networks with low assortativity tend to have nodes connecting with dissimilar degrees, making them more vulnerable to targeted attacks on high-degree nodes [...]" (Aldo Marzullo et al, "Graph Machine Learning" 2nd Ed., 2025)

"The concept of temporal graphs is useful in all the real-world problems that can be represented as a graph, where the nodes and edges of the graph may change over time. For example, temporal graphs are extensively applied in modeling social networks. By capturing the evolving relationships between individuals, temporal graphs enable a more accurate representation of social dynamics. This is particularly useful for predicting changes in friendships, community structures, and the information diffusion over time." (Aldo Marzullo et al, "Graph Machine Learning" 2nd Ed., 2025)

"The principle of common fate proposes that objects that move together or change similarly tend to be perceived as a group or a pattern. In this case, graphs that allow visualizing data obeying this principle will have to embody a type or a sense of motion. To illustrate this principle, let us consider a motion chart, a streamgraph, and a force‑directed graph. The motion chart is a visualization method that shows how data changes over time; the streamgraph is a stacked area graph that shows the changes in a set of data over time; and the force‑directed graph is a network visualization that shows the relationships of nodes in a graph. In all cases, there is a sense of common fate in the data." (Leandro N de Castro, "Exploratory Data Analysis: Descriptive Analysis, Visualization, and Dashboard Design", 2025)

🕸️On Graph Theory: On Graphs (-1999)

"As a simple trick, the discrete can often be carried over into the continuous, in a way suitable for practical purposes, by making a graph of the discrete, with the values shown as separate points. It is then easy to see the form that the changes will take if the points were to become infinitely numerous and close together." (W Ross Ashby, "An Introduction to Cybernetics", 1956)

"The concepts a person uses are represented as points, and the causal links between these concepts are represented as arrows between these points. This gives a pictorial representation of the causal assertions of a person as a graph of points and arrows. This kind of representation of assertions as a graph will be called a cognitive map. The policy alternatives, all of the various causes and effects, the goals, and the ultimate utility of the decision maker can all be thought of as concept variables, and represented as points in the cognitive map. The real power of this approach ap pears when a cognitive map is pictured in graph form; it is then relatively easy to see how each of the concepts and causal relation ships relate to each other, and to see the overall structure of the whole set of portrayed assertions." (Robert Axelrod, "The Cognitive Mapping Approach to Decision Making" [in "Structure of Decision: The Cognitive Maps of Political Elites"], 1976)

"A semantic network or net represents knowledge as a net-like graph. An idea, event, situation or object almost always has a composite structure; this is represented in a semantic network by a corresponding structure of nodes (drawn as circles or boxes) representing conceptual units, and directed links (drawn as arrows between the nodes) representing the relations between the units. […] An abstract (graph-theoretic) network can be diagrammed, defined mathematically, programmed in a computer, or hard-wired electronically. It becomes semantic when you assign a meaning to each node and link. Unlike specialized networks and diagrams, semantic networks aim to represent any kind of knowledge which can be described in natural language. A semantic network system includes not only the explicitly stored net structure but also methods for automatically deriving from that a much larger structure or body of implied knowledge." (Fritz Lehman, "Semantic Networks",  Computers & Mathematics with Applications Vol. 23 (2-5), 1992)

"The essential idea of semantic networks is that the graph-theoretic structure of relations and. abstractions can be used for inference as well as understanding. […] A semantic network is a discrete structure as is any linguistic description. Representation of the continuous 'outside world' with such a structure is necessarily incomplete, and requires decisions as to which information is kept and which is lost." (Fritz Lehman, "Semantic Networks",  Computers & Mathematics with Applications Vol. 23 (2-5), 1992)

"The idea of a planar graph, and other concepts which spring from that, bring together two areas of mathematics, graph theory (which is essentially the study of some relations) and the geometry of surfaces (which is part of topology). As often happens in mathematics, the marriage of two different disciplines results in some interesting (and sometimes rather difficult) offspring." (Victor Bryant, "Aspects of Combinatorics: S wide-ranging introduction", 1993)

"A graph is a good way to mathematically represent a physical situation in which there is a flow of something - materials, people, money, information – from one place to another." (John L Casti, "Five Golden Rules: Great Theories of 20th-Century Mathematics - and Why They Matter", 1995)

"Graph theory is typical of much modern mathematics. Its subject matter is not traditional, and it is not a development from traditional theories. Its applications are not traditional either. […] Graph theory is not concerned with continuous quantities. It often involves counting, but in integers, not measuring using fractions. Graph theory is an example of discrete mathematics. Graphs are put together in pieces, in chunks, rather like Meccano or Lego, or a jigsaw puzzle." (David Wells, "You Are a Mathematician: A wise and witty introduction to the joy of numbers", 1995)

"Depth First Search is especially appropriate for threading mazes, because it is possible to use it without having a map of the maze. It involves only local rules at nodes, plus a record of nodes and edges already used, so you can explore the graph and traverse it as you go. The name indicates the basic idea: give top priority to pushing deeper into the maze. The number of steps required is at most twice the number of passages in the maze." (Ian Stewart, "The Magical Maze: Seeing the world through mathematical eyes", 1997)

"Graphs are one of the unifying themes of computer science - an abstract representation that describes the organization of transportation systems, human interactions, and telecommunication networks. That so many different structures can be modeled using a single formalism is a source of great power to the educated programmer." (Steven S Skiena, "The Algorithm Design Manual", 1997)

"One very effective approach is to represent all the possible actions as a maze, and try to find a route through it. It is a logical maze rather than a real one, touched with that magic genius of mathematical transformations in which a problem that seems unassailable in one form becomes trivial in another, logically equivalent one. The idea is to represent the problem in a visual manner, using a diagram called a graph. A graph consists of a number of nodes (dots) linked by edges (lines), possibly with arrows on them. Each 'state' of the puzzle - position of the items of produce relative to the river - is represented by a node. Each 'legal' move between states is represented as an edge joining the corresponding nodes. If necessary, arrows can be added to the edges to show which is the starting state and which is the end state. The solution of the puzzle then reduces to tracing a path through its graph, starting from the initial state of the problem and finishing at the desired final state. The graph is a kind of conceptual map of the puzzle - a maze of possible states whose passages are the edges of the graph and whose junctions are its nodes." (Ian Stewart, "The Magical Maze: Seeing the World Through Mathematical Eyes", 1997)

"The three basic mechanisms of averaging, feedback and division of labor give us a first idea of a how a CMM [Collective Mental Map] can be developed in the most efficient way, that is, how a given number of individuals can achieve a maximum of collective problem-solving competence. A collective mental map is developed basically by superposing a number of individual mental maps. There must be sufficient diversity among these individual maps to cover an as large as possible domain, yet sufficient redundancy so that the overlap between maps is large enough to make the resulting graph fully connected, and so that each preference in the map is the superposition of a number of individual preferences that is large enough to cancel out individual fluctuations. The best way to quickly expand and improve the map and fill in gaps is to use a positive feedback that encourages individuals to use high preference paths discovered by others, yet is not so strong that it discourages the exploration of new paths." (Francis Heylighen, "Collective Intelligence and its Implementation on the Web", 1999)

"We wrote down all the states and legal moves (here it turned out to be helpful to have a systematic notation, but that's not essential). Then we formed a graph whose nodes correspond to states and whose edges correspond to legal moves. The solution of the puzzle is then a path through the graph that joins the start to the finish. Such a path is usually obvious to the eye, provided the puzzle is sufficiently simple for the entire graph to be drawn. Puzzles of this type are really mazes, for a maze is just a graph drawn in a slightly different fashion. Metaphorically, they are logical mazes - you have to find the right sequence of moves to solve them. The graph turns the logical maze into a genuine maze, turning the metaphor into reality. The fact that solving the real maze also solves the logical maze is one of the magical features of the maze that is mathematics." (Ian Stewart, "The Magical Maze: Seeing the World Through Mathematical Eyes", 1997)

🕸️On Graph Theory: On Graphs (2000-2012)

"Euler's proof that in Konigsberg there is no path crossing all seven bridges only once was based on a simple observation. Nodes with an odd number of links must be either the starting or the end point of the journey. A continuous path that goes through all the bridges can have only one starting and one end point. Thus, such a path cannot exist on a graph that has more than two nodes with an odd number of links. As the Konigsberg graph had four such nodes, one could not find the desired path." (Albert-László Barabási, "Linked: How Everything Is Connected to Everything Else and What It Means for Business, Science, and Everyday Life", 2002)

"Regular graphs are unique in that each node has exactly the same number of links. […] Such regularity is clearly absent from random graphs. The premise of the random network model is deeply egalitarian: We place the links completely randomly; thus all nodes have the same chance of getting one […] If the network is large, despite the links' completely random placement, almost all nodes will have approximately the same number of links." (Albert-László Barabási, "Linked: How Everything Is Connected to Everything Else and What It Means for Business, Science, and Everyday Life", 2002)

"'There is an old debate', Erdos liked to say, 'about whether you create mathematics or just discover it. In other words, are the truths already there, even if we don't yet know them?' Erdos had a clear answer to this question: Mathematical truths are there among the list of absolute truths, and we just rediscover them. Random graph theory, so elegant and simple, seemed to him to belong to the eternal truths. Yet today we know that random networks played little role in assembling our universe. Instead, nature resorted to a few fundamental laws, which will be revealed in the coming chapters. Erdos himself created mathematical truths and an alternative view of our world by developing random graph theory." (Albert-László Barabási, "Linked: How Everything Is Connected to Everything Else and What It Means for Business, Science, and Everyday Life", 2002)

"Undirected graphs are an alternative to directed graphs for representing independence relations. Since both directed and undirected graphs are used in practice, it is a good idea to be facile with both. The main difference between the two is that the rules for reading independence relations from the graph are different." (Larry A Wasserman, "All of Statistics: A concise course in statistical inference", 2004)

"In modern terminology, a collection of points in space (called vertices) and lines (called edges) joining selected pairs of those points is called a graph, and the study of graphs is called graph theory. A graph that can be drawn on the plane so that the joining lines intersect only at vertices is called a planar graph." (David Gay, "Explorations in Topology", 2007)

"The important graphs are the ones where some things are not connected to some other things. When the unenlightened ones try to be profound, they draw endless verbal comparisons between this topic, and that topic, which is like this, which is like that; until their graph is fully connected and also totally useless." (Eliezer S Yudkowsky,  "Mysterious Answers to Mysterious Questions", 2007)

"The general concept of a map is not so different from that of a model, though the one is extrapolated from a graph with spatial similarity to certain features of a landscape, and the other from a table-top contraption."  (Bas C van Fraassen, "Scientific Representation: Paradoxes of Perspective", 2008)

"A first step in understanding complex systems is trying to understand patterns and regularities of interactions in a way which might make it possible to break the systems down into possible subcomponents. To do so, it is necessary to find a way of representing complex systems. […] A convenient way to represent complex systems is through graphs or networks." (Jörg Reichardt, "Structure in Complex Networks", 2009)

"A graph in mathematics is a set of nodes and a set of edges between pairs of those nodes; the edges are ordered or nonordered pairs, or a relation, that defines the pairs of nodes for which the relation being examined is valid. […] The edges can either be undirected or directed; directed edges depict a relation that requires the nodes to be ordered while an undirected edge defines a relation in which no ordering of the edges is implied." (Dennis M Buede, "The Engineering Design of Systems: Models and methods", 2009)

"A graph enables us to visualize a relation over a set, which makes the characteristics of relations such as transitivity and symmetry easier to understand. […] Notions such as paths and cycles are key to understanding the more complex and powerful concepts of graph theory. There are many degrees of connectedness that apply to a graph; understanding these types of connectedness enables the engineer to understand the basic properties that can be defined for the graph representing some aspect of his or her system. The concepts of adjacency and reachability are the first steps to understanding the ability of an allocated architecture of a system to execute properly." (Dennis M Buede, "The Engineering Design of Systems: Models and methods", 2009)

"Democracy is a highly robust, but at the same time very fragile, complex system, which requires constant change to maintain its self-organized state. Democracy is by definition not in equilibrium. The random graph pattern may pose a system of boring and very low-complexity equilibrium. If all of us ever find ourselves with plenty of resources, that will be THE END of our history." (Péter Csermely, "Weak Links: The Universal Key to the Stabilityof Networks and Complex Systems", 2009)

"For the study of the topology of the interactions of a complex system it is of central importance to have proper random null models of networks, i.e., models of how a graph arises from a random process. Such models are needed for comparison with real world data. When analyzing the structure of real world networks, the null hypothesis shall always be that the link structure is due to chance alone. This null hypothesis may only be rejected if the link structure found differs significantly from an expectation value obtained from a random model. Any deviation from the random null model must be explained by non-random processes." (Jörg Reichardt, "Structure in Complex Networks", 2009)