🕸️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)

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

"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 difference between necessary and sufficient conditions seems an obvious one, yet they are surprisingly often confused in mathematical proofs. Formally, in graph theory, conditions are used to prove properties of graphs. When a condition C is said to be necessary, this means that a property P can hold only if C is met. When a condition C is said to be sufficient, this means that if C is met, then property P will hold true. And indeed, when property P is true if and only if condition C is met, indicates that C is a necessary and sufficient condition for property P to be valid." (Maarten van Steen, "Graph Theory and Complex Networks: An Introduction", 2010)

"Graphs are among the most important abstract data structures in computer science, and the algorithms that operate on them are critical to modern life. Graphs have been shown to be powerful tools for modeling complex problems because of their simplicity and generality." (Jeremy Kepner & John Gilbert [Eds],"Graph Algorithms in the Language of Linear Algebra", 2011)

"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)

"A network (or graph) consists of a set of nodes (or vertices, actors) and a set of edges (or links, ties) that connect those nodes. [...] The size of a network is characterized by the numbers of nodes and edges in it." (Hiroki Sayama, "Introduction to the Modeling and Analysis of Complex Systems", 2015)

"Node-link, matrix, and implicit representations are suited for different graph data. Node-link diagrams are good for sparse networks, which have a moderate number of edges. Dense networks with many edges are best visualized using a matrix. Trees, as we just said, are nicely represented by implicit approaches." (Christian Tominski & Heidrun Schumann, "Interactive Visual Data Analysis", 2019)

"Network theory confirms the view that information can take on 'a life of its own'. In the yeast network my colleagues found that 40 per cent of node pairs that are correlated via information transfer are not in fact physically connected; there is no direct chemical interaction. Conversely, about 35 per cent of node pairs transfer no information between them even though they are causally connected via a 'chemical wire' (edge). Patterns of information traversing the system may appear to be flowing down the 'wires' (along the edges of the graph) even when they are not. For some reason, 'correlation without causation' seems to be amplified in the biological case relative to random networks." (Paul Davies, "The Demon in the Machine: How Hidden Webs of Information Are Solving the Mystery of Life", 2019)

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

"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 extremely useful for encoding information, and data in graph format is increasingly plentiful. In many areas of machine learning - including natural language processing, computer vision, and recommendations - graphs are used to model local relationships between isolated data items (users, items, events, and so on) and to construct global structures from local information. Representing data as graphs is often a necessary step (and at other times only a desirable one) in dealing with problems arising from applications in machine learning or data mining." (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)

"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)

"Several areas of graph theory are concerned with the likelihood or certainty of the presence in a graph of various subgraphs or, more generally, of graph properties that emerge as the number of vertices and/or the number of edges increases. Collectively they are grouped as analytic graph theory." (Jonathan L Gross et al, "Topics in Graph Theory", 2023)

"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)

"[...] 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 point of caution when dealing with projections: be aware of the dimension of the projected graph.  In certain cases, such as the one we are considering here, projection may create extremely large numbers of edges, which makes the graph hard to be analyzed." (Aldo Marzullo et al, "Graph Machine Learning" 2nd Ed., 2025)

"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)

"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)

Alessandro Negro - Collected Quotes

"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)

"A widely adopted technique for solving the data sparsity issue and the cold-start problem is based on graph representation, navigation, and processing. Graph navigation methods (like the pathfinding example [...]) and graph algorithms (such as PageRank) are applied to fill some gaps and create a denser representation of [a] dataset."

"GNNs are capable of generating representations of nodes that depend on the structure of the graph as well as on any feature information we have. These features could be nodes’ properties, relationship types, and relationship properties. That’s why GNNs could drive the final tasks to better results. These embeddings represent the input for tasks such as node classification, link prediction, and graph classification." (Alessandro Negro, "Graph-Powered Machine Learning", 2021)

"[...] graphs are extremely useful for encoding information, and data in graph format is increasingly plentiful. In many areas of machine learning - including natural language processing, computer vision, and recommendations - graphs are used to model local relationships between isolated data items (users, items, events, and so on) and to construct global structures from local information. Representing data as graphs is often a necessary step (and at other times only a desirable one) in dealing with problems arising from applications in machine learning or data mining." (Alessandro Negro, "Graph-Powered Machine Learning", 2021)

"Graphs are powerful structures useful not only for representing connected information, but also for supporting multiple types of analysis. Their simple data model, consisting of two basic concepts such as nodes and relationships, is flexible enough to store complex information. If you also store properties in nodes and relationships, it is possible to represent practically everything of any size." (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)

"Graphs can be used to model and analyze the relationships between entities as well as their properties. This aspect brings an additional dimension of information that graph-powered machine learning can harness for prediction and categorization. The schema flexibility provided by graphs also allows different models to coexist in the same dataset." (Alessandro Negro, "Graph-Powered Machine Learning", 2021)

"Graphs can support machine learning by doing what they do best: representing data in a way that is easily understandable and easily accessible. Graphs make all the necessary processes faster, more accurate, and much more effective. Moreover, graph algorithms are powerful tools for machine learning practitioners. Graph community detection algorithms can help identify groups of people, page rank can reveal the most relevant keywords in a text, and so on." (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)

"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)

James G Scott - Collected Quotes

"A model is a metaphor, a description of a system that helps us to reason more clearly. Like all metaphors, models are approximations, and will never account for every last detail. A useful mantra here is: all models are wrong, but some models are useful." (James G Scott, "Statistical Modeling: A Gentle Introduction", 2017)

"[...] always remember that the construction of an ANOVA table is inherently sequential. For example, first we add the clutter variable, which remains in the model at every subsequent step; then we add the distance variable, which remains in the model at every subsequent step; and so forth. Thus the actual question being answered at each stage of an analysis of variance is: how much variation in the response can this new variable predict, in the context of what has already been predicted by other variables in the model? This point - the importance of context in interpreting an ANOVA table - is subtle, but important." (James G Scott, "Statistical Modeling: A Gentle Introduction", 2017)

"An obvious question is: do bootstrapped confidence intervals satisfy the frequentist coverage property? If your sample is fairly representative of the population, then the answer is a qualified yes. That is, the bootstrapping procedure yields nominal X% intervals that cover the true value 'approximately' X% of the time. Moreover, as the size of the original sample gets bigger, the quality of the approximation gets better. Alas, it is necessary to appeal to some very advanced probability theory to put both of these claims on firm footing." (James G Scott, "Statistical Modeling: A Gentle Introduction", 2017)

"At the core of the resampling approach to statistical inference lies a simple idea. Most of the time, we can’t feasibly take repeated samples of size n from the population, to see how our estimate changes from one sample to the next. But we can repeatedly take samples of size n from the sample itself, and apply our estimator afresh to each notional sample. The idea is that the variability of the estimates across all these samples can be used to approximate our estimator’s true sampling distribution. This process - pretending that our sample is the whole population, and taking repeated samples of size n with replacement from our original sample of size n - is called bootstrap resampling, or just bootstrapping" (James G Scott, "Statistical Modeling: A Gentle Introduction", 2017)

"By themselves, sums of squares are hard to interpret, because they are measured in squared units of the Y variable. But their ratios are highly meaningful. In fact, the ratio of PV to TV - or what fraction of the total variation has been predicted by the model - is one of the most frequently quoted summary measures in all of statistical modeling. This ratio is called the coefficient of determination, and is usually denoted by the symbol R2 [...] The correct interpretation of R2 sometimes trips people up, and is therefore worth repeating: it is the proportion of variance in the data that can be predicted using the statistical model in question." (James G Scott, "Statistical Modeling: A Gentle Introduction", 2017)

"Good estimators are those that usually yield estimates close to the truth, with minimal variation. Therefore, we typically summarize a sampling distribution using its standard deviation, which we refer to as the standard error. In quoting the standard error of an estimator’s sampling distribution, you are saying: 'If I were to take repeated samples from the population and use this estimatorfor every sample, my estimate is typically off from the truth by about this much.' Notice again that this is a claim about a procedure, not a particular estimate. The bigger the standard error, the less stable the estimator across different samples, and the less you can trust the estimate for any particular sample." (James G Scott, "Statistical Modeling: A Gentle Introduction", 2017)

"In fitting statistical models, we typically equate the trustworthiness of a procedure with its stability under the influence of luck, and we seek to measure the degree to which that procedure might have given a different answer if the forces of randomness had made the world look a bit different. Specifically, the question we seek to answer is: 'if our data set had been different merely due to chance, would our answer have been different, too?'" (James G Scott, "Statistical Modeling: A Gentle Introduction", 2017)

"Model-building requires much more than just technical knowledge of statistical ideas. It also requires care and judgment, and cannot be reduced to a flowchart, a table of formulas, or a tidy set of numerical summaries that wring every last drop of truth from a data set. There is almost never a single 'right' statistical model for some problem. But there are definitely such things as good models and bad models, and learning to tell the difference is important. Just remember: calling a model good or bad requires knowing both the tool and the task." (James G Scott, "Statistical Modeling: A Gentle Introduction", 2017)

"[...] complexity sometimes comes at the expense of explanatory power. We must avoid building models calibrated so perfectly to past experience that they do not generalize to future cases." (James G Scott, "Statistical Modeling: A Gentle Introduction", 2017)

"It is common to view a statistical model as nothing more than a recipe for calculating the fitted values, and to think that the residuals are just the errors made by this model. But we’ll have a richer picture if instead we view the residuals as part of the model. If you’ve ignored the variation in the residuals, then you really haven’t specified a complete forecast." (James G Scott, "Statistical Modeling: A Gentle Introduction", 2017)

"Resampling won’t yield the true sampling distribution of an estimator, but it is often good enough for approximating the standard error (which you’ll remember is just the standard deviation of the sampling distribution). We use the term bootstrapped standard error for the standard deviation of the bootstrapped sampling distribution. The bootstrapped standard error is an estimate of the true standard error." (James G Scott, "Statistical Modeling: A Gentle Introduction", 2017)

"Tables are almost always the best way to display categorical data sets with few classifying variables, for the simple reason that they convey a lot of information in a small space." (James G Scott, "Statistical Modeling: A Gentle Introduction", 2017)

"The residuals from a regression model are sometimes called 'errors'. This is especially true in experimental science, where measurements of some Y variable will be taken at different values of the X variable (called design points), and where noisy measurement instruments can introduce random errors into theobservations. But in many cases this interpretation of a residual as an error can be misleading. A regression model can still give a nonzero residual, even if there is no mistake in the measurement of the Y variable. It’s often far more illuminating to think of the residual as the part of the Y variable that it is left unpredicted by X." (James G Scott, "Statistical Modeling: A Gentle Introduction", 2017)