Quotable Mathematics: graphs

Showing posts with label graphs. Show all posts

14 October 2026

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

"When the graph is embedded within a surface it is called a map. The nature of the surface needed to embed the graph without crossing edges is a topological feature, and the topological structure of this payoff space is not only useful, but also beautiful." (David Robinson & David Goforth, "The Topology of the 2×2 Games: A New Periodic Table", 2005)

"The Simplicial Approximation Theorem is a concise statement of the general result for functions between any two triangulated spaces. It says that on a suitable subdivision of the domain, any continuous function can be homotopically deformed by an arbitrarily small amount so that the modified function sends vertices to vertices and is linear on each edge, face, tetrahedron, and higher-dimensional cell of the triangulation." (Robert Messer & Philip Straffin, "Topology Now!", 2006)

"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 ingredients of a map - on sphere, a rectangle, or an island - are countries, borders, and vertices. A country is the interior of a polygon or distorted polygon. The countries of a map do not overlap. A border of the map is an edge of one or more of the country polygons. Two countries may meet along one of these borders. A vertex of the map is where two or more borders meet. The map is the union of all these elements." (David Gay, "Explorations in Topology", 2007)

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

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

"A fuzzy cognitive map or FCM draws a causal picture. It ties facts and things and processes to values and policies and objectives. And it lets you predict how complex events interact and play out. [...] Neural nets give a shortcut to tuning an FCM. The trick is to let the fuzzy causal edges change as if they were synapses in a neural net. They cannot change with the same math laws because FCM edges stand for causal effect not signal flow. We bombard the FCM nodes with real data. The data state which nodes are on or off and to which degree at each moment in time. Then the edges grow among the nodes." (Bart Kosko, "Fuzzy Thinking: The new science of fuzzy logic", 1993)

"The euler characteristic is strikingly easy to compute, and it really seems odd that it should be a topological invariant. After all, it is computed from a cell decomposition, and it is very easy to come up with a lot of different complexes on a single surface, all with varying numbers of faces, edges, and vertices. But somehow by taking the alternating sum, one arrives at a quantity which depends only on the underlying shape and not on the particular complex." (L Christine Kinsey. "Topology of Surfaces", 1993)

"The four-color map theorem is an assertion about graph theory, which is the study of discrete points and the lines that connect them; each point is called a vertex and each line is called an edge." (Alexander Humez et al, "Zero to Lazy Eight: The romance of numbers", 1993)

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

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

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

"The key to generating the small-world phenomenon is the presence of a small fraction of [...] edges, which contact otherwise distant parts of the graph" (Duncan J Watts, "Small Worlds: The Dynamics of Networks Between Order and Randomness", 1999)

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

"A feedback loop is a cycle in a directed graph whose edges can represent either positive or negative inputs." (Maria C A Leite & Yunjiao Wang, "Multistability, oscillations and bifurcations in feedback loops", Mathematical Biosciences and Engineering Vol 7 (1), 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)

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

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

"Our assumptions are unquestionably interconnected. They are nodes with connections (edges) to other nodes. The more foundational the assumption, the more strongly connected it is. What I’m suggesting is that our assumptions and the highly sensitive network of responses, perceptions, behaviors, thoughts, and ideas they create and interact with are a complex system. One of the most basic features of such a network is that when you move or disrupt one thing that is strongly connected, you don’t just affect that one thing, you affect all the other things that are connected to it. Hence small causes can have massive effects (but they don’t have to, and usually don’t actually). In a system of high tension, simple questions targeting basic assumptions have the potential to transform perception in radical and unpredictable ways." (Beau Lotto, "Deviate: The Science of Seeing Differently", 2017)

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

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

"[...] 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)

🕸️On Graph Theory: On Edges (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 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)

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

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

"Hierarchical clustering is summarised by a dendrogram, which sequentially shows points being joined to form a cluster, with the corresponding distances. Breaking the data into clusters is done by cutting the dendrogram at the long edges. [...] Plotting the dendrogram in the data space can help you understand how the hierarchical clustering has collected the points together into clusters. You can learn if the algorithm has been confused by nuisance patterns in the data, and how different choices of linkage method affect the result." (Dianne Cook & Ursula Laa, "Interactively Exploring High-Dimensional Data and Models in R", 2026)

"Viewing the dendrograms in high dimensions provides insight into how the algorithm has joined points to clusters. For example, single linkage often has edges leading to a single focal point, which might not yield a useful clustering but might help to identify outliers. If the edges point to multiple focal points, with long edges bridging gaps in the data, the result is more likely yielding a useful clustering." (Dianne Cook & Ursula Laa, "Interactively Exploring High-Dimensional Data and Models in R", 2026)

11 October 2026

🕸️On Graph Theory: On Knowledge Graphs

"Knowledge graphs are a specific type of graph with an emphasis on contextual understanding. Knowledge graphs are interlinked sets of facts that describe real-world entities, events, or things and their interrelations in a human- and machine-understandable format." (Jesús Barrasa et al, "Knowledge Graphs: Data in Context for Responsive Businesses", 2021)

"[…] knowledge graphs are useful because they provide contextualized understanding of data. They achieve this by adding a layer of metadata that imposes rules for structure and interpretation." (Jesús Barrasa et al, "Knowledge Graphs: Data in Context for Responsive Businesses", 2021)

"Knowledge graphs use an organizing principle so that a user" (or a computer system) can reason about the underlying data. The organizing principle gives us an additional layer of organizing data (metadata) that adds connected context to support reasoning and knowledge discovery. […] Importantly, some processing can be done without knowledge of the domain, just by leveraging the features of the property graph model" (the organizing principle)." (Jesús Barrasa et al,Knowledge Graphs: Data in Context for Responsive Businesses", 2021)

"Data Fabric architecture utilizes active metadata, knowledge graphs, and semantic enrichment, combining intelligent information integration and transformation technologies to intelligently support data consumers, for example, business users." (Eberhard Hechler et al, "Data Fabric and Data Mesh Approaches with AI", 2023)

"In Exploiting semantic knowledge graphs can support interpretability and explainability of nearly all AI model types (including DL models) by discovering and depicting semantic and non-obvious relationships or depicting an ML model in a simplified and more readable, explainable way., a Data Mesh solution organizes data around business domain owners and transforms relevant data assets (data sources) to data products that can be consumed by distributed business users from various business domains or functions. These data products are created, governed, and used in an autonomous, decentralized, and self-service manner. Self-service capabilities, which we have already referenced as a Data Fabric capability, enable business organizations to entertain a data marketplace with shopping-for-data characteristics." (Eberhard Hechler et al, "Data Fabric and Data Mesh Approaches with AI", 2023)

"It is essential to realize that the Data Fabric architecture enables the Data Mesh solution via its rich knowledge catalog, semantic search and discovery, smart integration capabilities, and semantic knowledge graphs. Trustworthy AI, for instance, is enabled via the Data Fabric as well." (Eberhard Hechler et al, "Data Fabric and Data Mesh Approaches with AI", 2023)

"As with many other deep learning-based approaches, another major challenge is in interpretability. While knowledge graphs provide a structured and transparent way to store relationships, LLMs operate as a black box, making it difficult to understand how specific outputs are generated. [...] Data alignment is also a key issue, as structured knowledge graphs and unstructured text data must be carefully preprocessed to ensure consistency. Differences in data formats, ontology mismatches, and information redundancy can create inefficiencies when integrating these two paradigms. Developing robust pipelines that seamlessly connect graph-based insights with LLM-generated text remains an open challenge." (Aldo Marzullo et al, "Graph Machine Learning" 2nd Ed., 2025)

"Despite their impressive capabilities, LLMs are not without limitations. One of the most significant challenges is the problem of hallucination, where an LLM generates factually incorrect or misleading information that appears plausible. This is particularly problematic in domains requiring high factual accuracy, such as healthcare, finance, and legal applications. To mitigate hallucinations and enhance the reliability of LLM outputs, Retrieval-Augmented Generation (RAG) has emerged as a powerful technique. RAG works by dynamically retrieving relevant information from an external knowledge source (such as a knowledge graph) at inference time, rather than just relying on pre-trained knowledge. This approach ensures that the model has access to up-to-date and accurate data, grounding answers in verified information rather than generating content purely from its internal representations." (Aldo Marzullo et al, "Graph Machine Learning" 2nd Ed., 2025)

"Despite their effectiveness and advantages in supporting the development of intelligent systems, KGs haven’t been widely adopted for several reasons, including the following: (•) They are expensive to build and maintain in terms of time, effort, and money. (•) Intricate access patterns are required to navigate multiple hops. (•) Their results scatter information across multiple nodes and relationships." (Alessandro Negro, "Graph-Powered Machine Learning", 2021)

"Generative artificial intelligence (GenAI), powered by large language models (LLMs) like Google’s Gemini and OpenAI’s GPT, has transformed how we work and live, revolutionizing business after business. Despite this success, generative AI falls short in domains where specific domain knowledge, high accuracy, and explainability are essential. And it has other significant limitations, including hallucinations and a lack of context and relations. This is where knowledge graphs (KGs) come in, provid-ing contextual information - such as experiences, environmental characteristics, cultural aspects, and social normsneeded to build the 'third wave of AI' for mission-critical applications." (Alessandro Negro et al, "Knowledge Graphs and LLMs in Action", 2026)

"KGs are sophisticated graph structures that represent real-world entities (people, places, diseases, proteins), define meaningful connections between them, and provide context. KGs provide structured, explainable knowledge representation but are challenging to build and query; LLMs offer natural language processing capabilities but suffer from hallucinations, stale information, and a lack of domain-specific grounding. Together, they are a 'killer combination': LLMs can extract entities and relationships from unstructured text to build KGs more efficiently, providing more autonomous and powerful graph querying and analysis. Meanwhile, KGs provide reliable, up-to-date domain knowledge to ground LLM responses and prevent hallucinations." (Alessandro Negro et al, "Knowledge Graphs and LLMs in Action", 2026)

"The KG serves as the central reference for all structured and unstructured data related to a domain. Because a KG represents information by focusing on the meaning of data, users can overcome challenges related to data types, formats, and provenance, connecting information from multiple data sources. [...] A KG represents the core information and big picture of a domain. Humans can analyze, visualize, and query graph data to extract insights. Inference rules and machine learning algorithms are performed on top of the KG to infer new information not explicitly encoded within the KG. Analysts can use methods such as centrality and connectivity analysis to identify influential nodes, network analysis to detect the shortest path between nodes, and community analysis to recognize groups of similar nodes." (Alessandro Negro et al, "Knowledge Graphs and LLMs in Action", 2026)

"Traditional paradigms build systems for specific purposes with structured, homogeneous databases. This approach works for tailored needs but is impractical for complex domains that need to adapt to user characteristics and integrate heterogeneous data. KGs capture connections, enabling relationship discovery through graph pattern matching and traversal. Both the Resource Description Framework (RDF) and Labeled Property Graphs (LPGs) provide machine-readable formats that humans can interpret. KGs emphasize rich, meaningful data representations usable by both humans and machines, enabling a paradigm shift where intelligent behavior is encoded in a unique source of truth." (Alessandro Negro et al, "Knowledge Graphs and LLMs in Action", 2026)

🕸️On Graph Theory: On Vertices

"Moonshine forms a way of explaining the mysterious connection between the monster finite group and modular functions from classical number theory. The theory has evolved to describe the relationship between finite groups, modular forms and vertex operator algebras." (Terry Gannon, "Moonshine Beyond the Monster: The Bridge Connecting Algebra, Modular Forms and Physics", 2006)

"We investigate structure in the network by characterizing motifs that represent order. A simple motif is the existence of a triangle, three vertices connected one to the next. The ratio of the number of observed to expected triangles is synonymous with the standard definition of the clustering coefficient for a small world network. This statistic is sensitive to organization over short length scales. To investigate organization over longer length scales, we investigate the distribution of longer cycles. This distribution may be measured for an empirical network We introduce a simple mathematical model for a network organized to have one level of clustering and show that this model is sufficient to explain the observed cycle distribution. Thus, there is no need to invoke a continuous distribution of length scales. Moreover, the one-level model immediately yields a characteristic, testable scaling length for the network, which again stands in contrast to scale-free behavior." (J S Bader, "The Drosophila Protein Interaction Network May Be neither Power-Law nor Scale-Free", 2006)

"A major idea [...] is the equivalency of two maps, one a stretchedshrunk version of the other. This is an instance of 'rubber sheet' geometry. Print your map on a thin sheet of rubber, and then distort the rubber sheet to get other equivalent maps. The distortion preserves the countries, borders, vertices, and their relationships to each other. However, the distortion does not preserve exact distances or angles. The investigation of geometric properties preserved under this notion of geometric equivalence was first proposed by Leibnitz [...]. He called the study of such properties, geometria situs. The modern word is topology." (David Gay, "Explorations in Topology", 2007)

"In the web graph, each vertex acts as an independent agent, which will base its decision on how to link to the existing network on local knowledge. As a result, the neighbourhood of a new vertex will often be an imperfect copy of the neighbourhood of an existing vertex. This aspect of web page generation indicates a weakness of preferential attachment models: we assume global knowledge of all vertex degrees, a clearly unrealistic hypothesis when faced with a massive set of vertices. Both the copying models of the web graph, and the duplication model for biological networks incorporate this notion of copying in their definitions." (Anthony Bonato, "A Course on the Web Graph", 2008)

"These networks arise naturally in many diverse disciplines (such as biology, computer science, and social science), but all share the common characteristics of being massive, sparse graphs with a power law degree distribution and small world structure. Such networks have now been coined scale-free, complex, self-organizing, or heterogeneous. Our own preferred term is self-organizing, since this is suggestive of the generative mechanisms underlying the network: over time, vertices choose their neighbour according to their own predisposition, rather than necessarily following global rules." (Anthony Bonato, "A Course on the Web Graph", 2008)

10 October 2026

Anthony Bonato - Collected Quotes

"A side effect of computing in a small world web is vulnerability to viruses or other malicious software. A computer virus may be broadly defined as a program that can replicate itself while executing instructions on infected computers, without the user's knowledge. Modelling computer viruses may lead to new methods to combat them. How can we model computer viruses loose on scale-free networks?" (Anthony Bonato, "A Course on the Web Graph", 2008)

"An open problem is to design a rigorous graph model which simulates properties of physical networks such as the various levels of the internet graph. For example, any model of the internet should take into account the technological and economic constraints at work (which are more important in this context than in W)." (Anthony Bonato, "A Course on the Web Graph", 2008)

"As any mathematician can tell you, there is more to probability than gam- bling. Indeed, applications of probability theory are now common in both graph theory and theoretical computer science." (Anthony Bonato, "A Course on the Web Graph", 2008)

"Graph theory contains a myriad of elegant proofs using probabilistic methods, especially when other techniques are not applicable. An advantage of randomized methods is their ability to prove the existence of some object without explicitly constructing it." (Anthony Bonato, "A Course on the Web Graph", 2008)

"Infinite graphs possess their own rich theory which is quite different in many aspects from the finite case. [...] we will discuss some of these aspects, then attempt to apply infinite graphs to web graph theory. The approach is new and different, but we think it has and will lead to interesting mathematics and to better insights into Wand its models. As is often the case in internet mathematics, results are Inore suggestive than definitive." (Anthony Bonato, "A Course on the Web Graph", 2008)

"Preferential attachment is one of the main paradigms used in the design of web graph models. Hence, it is natural to consider limits of on-line preferential attachment models." (Anthony Bonato, "A Course on the Web Graph", 2008)

"Regardless of the finiteness of the universe, the view of W as an infinite graph presents an interesting perspective for the mathematician. Infinite graphs are fascinating creatures whose properties are often bewildering and quite unlike finite ones." (Anthony Bonato, "A Course on the Web Graph", 2008)

"Speaking of the web graph is somewhat mis- leading, as the web is an evolving structure with pages and links appearing and disappearing continuously over time. We will overlook such concerns." (Anthony Bonato, "A Course on the Web Graph", 2008)

"The presence of power law degree distributions reflects a certain undemocratic aspect of W: while most pages have a small number of links, a few pages have a large number. This is in hindsight not surprising, since the choice of links from new pages to existing ones is determined by the users' own interests. For example, it seems plausible that popular pages attract more new links than unpopular ones." (Anthony Bonato, "A Course on the Web Graph", 2008)

"The web contains a seemingly infinite ocean of information. Traversing this ocean unaided would be difficult if not impossible. As most of us experience on a daily basis, search engines are an invaluable tool to surf the vast storehouse of information available online." (Anthony Bonato, "A Course on the Web Graph", 2008)

"The web contains many communities: sets of pages sharing a common interest or topic. However, there is no consensus for a precise definition of a community in the web graph." (Anthony Bonato, "A Course on the Web Graph", 2008).

🕸️On Graph Theory: On Density

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

"Inclusiveness simply measures the number or proportion of the whole set of points that are actually connected into one or more parts of the graph. Some points may be isolates, having no ties to other points, while others will be connected, to a greater or lesser extent, into larger structures. The inclusiveness of a graph is simply the total number of non-isolated points, gener-ally expressed as a percentage of the total number of points. Inclusiveness is a rough and ready approximation to cohesion, but it is usually more informative to measure the actual density of the graph." (John Scott," What is Social Network Analysis?", 2012)

"The density of a graph is a very useful and direct measure of its cohesion, but it has one major limitation as a comparative measure of social structure. In real situations, density varies with the size of a network and this limits the possibilities of using the measure to compare different types of network. It is highly unlikely that agents are able to sustain more than a certain number of relationships: our ability to be ‘friends’ with people, for example, has its limits." (John Scott," What is Social Network Analysis?", 2012)

"Linking is a powerful dynamic interactive graphics technique that can help us better understand high-dimensional data. This technique works in the following way: When several plots are linked, selecting an observation's point in a plot will do more than highlight the observation in the plot we are interacting with - it will also highlight points in other plots with which it is linked, giving us a more complete idea of its value across all the variables. Selecting is done interactively with a pointing device. The point selected, and corresponding points in the other linked plots, are highlighted simultaneously. Thus, we can select a cluster of points in one plot and see if it corresponds to a cluster in any other plot, enabling us to investigate the high-dimensional shape and density of the cluster of points, and permitting us to investigate the structure of the disease space." (Forrest W Young et al, "Visual Statistics: Seeing data with dynamic interactive graphics", 2016)

"When using community detection algorithms, be conscious of the density of the relationships. If the graph is very dense, you may end up with all nodes congregating in one or just a few clusters. You can counteract this by filtering by degree, relationship weights, or similarity metrics. On the other hand, if the graph is too sparse with few connected nodes, you may end up with each node in its own cluster. In this case, try to incorporate additional relationship types that carry more relevant information." (Mark Needham & Amy E Hodler, "Graph Algorithms: Practical Examples in Apache Spark and Neo4j", 2019)

09 October 2026

🕸️On Graph Theory: On Neighborhoods

"[...] the transition to a small world is essentially undetectable at a local level. If you were living through the morph, nothing about your immediate neighborhood would tell you that the world had become small." (Steven Strogatz, "Sync: The Emerging Science of Spontaneous Order", 2003)

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

"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 whole collection of global measures cluster around the idea of the centrality of points within their graphs. The degree of a point - its total of incoming and outgoing lines—is the most basic measure and has been termed local centrality. Calculating the degrees of all points in a network and ranking them from highest to lowest gives a rank order of local centrality. This centrality is ‘local’ because it highlights points that are well-connected in their immediate neighbourhoods. Such points may not, however, be central in the more global sense that a circle or sphere has a unique centre that can be understood in quasi-spatial terms. Locally central points are well-connected within particular parts of the network but may not be at all well-connected in a global sense." (John Scott," What is Social Network Analysis?", 2012)

"Typically, most outlier detection algorithms use some quantified measure of the outlierness of a data point, such as the sparsity of the underlying region, nearest neighbor based distance, or the fit to the underlying data distribution. Every data point lies on a continuous spectrum from normal data to noise, and finally to anomalies [...] The separation of the different regions of this spectrum is often not precisely defined, and is chosen on an ad-hoc basis according to application-specific criteria. Furthermore, the separation between noise and anomalies is not pure, and many data points created by a noisy generative process may be deviant enough to be interpreted as anomalies on the basis of the outlier score. Thus, anomalies will typically have a much higher outlier score than noise, but this is not a distinguishing factor between the two as a matter of definition. Rather, it is the interest of the analyst, which regulates the distinction between noise and an anomaly." (Charu C Aggarwal, "Outlier Analysis", 2013)

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

"Decision trees are also discriminative models. Decision trees are induced by recursively partitioning the feature space into regions belonging to the different classes, and consequently they define a decision boundary by aggregating the neighboring regions belonging to the same class. Decision tree model ensembles based on bagging and boosting are also discriminative models." (John D Kelleher et al, "Fundamentals of Machine Learning for Predictive Data Analytics: Algorithms, Worked Examples, and Case Studies", 2015)

"A random walk, in general, is sometimes described as being similar to how a drunk person traverses a city. They know what direction or end point they want to reach but may take a very circuitous route to get there. The algorithm starts at one node and somewhat randomly follows one of the relationships forward or backward to a neighbor node. It then does the same from that node and so on, until it reaches the set path length. 'We say somewhat randomly because the number of relationships a node has, and its neighbors have, influences the probability a node will be walked through.)'" (Mark Needham & Amy E Hodler, "Graph Algorithms: Practical Examples in Apache Spark and Neo4j", 2019)

"Vector databases are designed to store and index highdimensional embeddings - dense numeric vectors that capture the semantic meaning of text, images, audio, or other content. Instead of looking for exact matches, they use approximate nearest neighbor (ANN) algorithms to return the items whose vectors lie closest to a query vector in that multidimensional space. This makes them the engine behind semantic search, recommendation systems, image-or-audio similarity matching, and retrieval augmented generation (RAG) pipelines that supply LLM prompts with relevant context in milliseconds." (Abi Aryan, "LLMOps: Managing Large Language Models in Production", 2025)

🕸️On Graph Theory: On Centrality

"A further measure of global cohesion is the centralisation of a network. Where centrality relates to the position of particular points, centralisation relates to the overall structure of a network. Centralisation measures the extent to which the cohesion of a network is organised around a specific point or set of connected points. The spokes on a bicycle wheel, for example, form a highly centralised network around its hub. Measures of centralisation can be based on the degree, distance, or betweenness of points, and extensions of these concepts have involved the idea that it is possible to identify the sets of points that comprise the centre, margin, and periphery of the network as a whole." (John Scott," What is Social Network Analysis?", 2012)

"The converse of centrality is peripherality and it can be useful to know those points that are least close to other members of their networks. Such points are not isolated but are poorly integrated into their network. They are likely to have little influ-ence and to be uninvolved in significant communication flows through the network." (John Scott," What is Social Network Analysis?", 2012)

"Betweenness Centrality makes the assumption that all communication between nodes happens along the shortest path and with the same frequency, which isn’t always the case in real life. Therefore, it doesn’t give us a perfect view of the most influential nodes in a graph, but rather a good representation." (Mark Needham & Amy E Hodler, "Graph Algorithms: Practical Examples in Apache Spark and Neo4j", 2019)

"Centrality algorithms are used to understand the roles of particular nodes in a graph and their impact on that network. They’re useful because they identify the most important nodes and help us understand group dynamics such as credibility, accessibility, the speed at which things spread, and bridges between groups." (Mark Needham & Amy E Hodler, "Graph Algorithms: Practical Examples in Apache Spark and Neo4j", 2019)

"Keep in mind that centrality measures represent the importance of a node in comparison to other nodes. Centrality is a ranking of the potential impact of nodes, not a measure of actual impact. For example, you might identify the two people with the highest centrality in a network, but perhaps policies or cultural norms are in play that actually shift influence to others. Quantifying actual impact is an active research area to develop additional influence metrics." (Mark Needham & Amy E Hodler, "Graph Algorithms: Practical Examples in Apache Spark and Neo4j", 2019)

"Sometimes the most important cog in the system is not the one with the most overt power or the highest status. Sometimes it’s the middlemen that connect groups or the brokers who the most control over resources or the flow of information. Betweenness Centrality is a way of detecting the amount of influence a node has over the flow of information or resources in a graph. It is typically used to find nodes that serve as a bridge from one part of a graph to another." (Mark Needham & Amy E Hodler, "Graph Algorithms: Practical Examples in Apache Spark and Neo4j", 2019)

"Use Degree Centrality if you’re attempting to analyze influence by looking at the number of incoming and outgoing relationships, or find the 'popularity' of individual nodes. It works well when you’re concerned with immediate connectedness or near-term probabilities. However, Degree Centrality is also applied to global analysis when you want to evaluate the minimum degree, maximum degree, mean degree, and standard deviation across the entire graph." (Mark Needham & Amy E Hodler, "Graph Algorithms: Practical Examples in Apache Spark and Neo4j", 2019)

🕸️On Graph Theory: On Small-Worlds

“The key to generating the small-world phenomenon is the presence of a small fraction of [...] edges, which contact otherwise distant parts of the graph” (Duncan J Watts, "Small Worlds: The Dynamics of Networks Between Order and Randomness", 1999)

"These networks arise naturally in many diverse disciplines (such as biology, cOInputer sci- ence, and social science), but all share the common characteristics of be- ing Inassive, sparse graphs with a power law degree distribution and small world structure. Such networks have now been coined scale-free, complex, self-organizing, or heterogeneous. Our own preferred term is self-organizing, since this is suggestive of the generative mechanisms underlying the network: over time, vertices choose their neighbour according to their own predisposition, rather than necessarily followil1g global rules." (Anthony Bonato, "A Course on the Web Graph", 2008)

"To put it simply, a small world is characterized by the fact that every two people can reach each other through a chain of just a handful of messages. This phenomenon is also known as the 'six degrees of separation' […]" (Maarten van Steen, "Graph Theory and Complex Networks: An Introduction", 2010)

"With the birth of Internet-based social networks, information on personal interaction on a large-scale became available and the interest in developing mathematical models that are able to capture and explain certain stylized features of large and complex real-world networks has grown significantly. Among the most central phenomena observed in large-scale real-world networks is the so-called small-world phenomenon, which refers to the fact that despite the large network size most of the nodes have a surprisingly small graph (hop count) distance in between them, and the so-called scale-free nature of networks, meaning that the degree sequence has polynomial decay." (Francesca Biagini et al (Eds), "Network Science: An Aerial View", 2019)

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

16 August 2026

🕸️On Graph Theory: On Semantic Networks (1990-)

"[…] semantic nets fail to be distinctive in the way they (1) represent propositions, (2) cluster information for access, (3) handle property inheritance, and (4) handle general inference; in other words, they lack distinctive representational properties (i.e., 1) and distinctive computational properties (i.e., 2-4). Certain propagation mechanisms, notably 'spreading activation', 'intersection search', or 'inference propagation' have sometimes been regarded as earmarks of semantic nets, but since most extant semantic nets lack such mechanisms, they cannot be considered criterial in current usage." (Lenhart K Schubert, "Semantic Nets are in the Eye of the Beholder", 1990)

"[…] the representational and computational strategies employed in semantic net systems are abstractly equivalent to those employed in virtually all state-of-the-art systems incorporating a substantial propositional knowledge base, whether they are described as logic-based, frame-based, rule-based, or some-thing else." (Lenhart K Schubert, "Semantic Nets are in the Eye of the Beholder", 1990)

"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 great organizing principle of thought is abstraction. By assigning particular things to abstract categories we are able to dispense with irrelevant detail and yet instantly draw copious conclusions about a thing due to its membership in various categories. Semantic networks specify the structure of interrelated abstract categories and use this structure to draw conclusions." (Fritz Lehman, "Semantic Networks", Computers & Mathematics with Applications Vol. 23 (2-5), 1992)

"Conceptual graphs are system of logic based on the existential graphs of Charles Sanders Peirce and the semantic networks of artificial intelligence. The purpose of the system is to express meaning in a form that is logically precise, humanly readable, and computationally tractable. With their direct mapping to language, conceptual graphs can serve as an intermediate language for translating computer-oriented formalisms to and from natural languages. With their graphic representation, they can serve as a readable, but design and specification language." (John F Sowa, "Conceptual graphs for knowledge representation", 1993)

"A knowledge modeling approach based on semantic networks and first-order logic, first introduced by Sowa, whereby knowledge is represented by concepts and relations linked together in a bipartite graph." (Harry S Delugach, "Formal Analysis of Workflows in Software Development", 2009

"Conceptual graphs consist of a formal language to access knowledge and meaning. A conceptual graph is a graph or network of two kinds of nodes, concepts and relations. They have the full power of first-order logic and can represent model and higher-order logic. Conceptual graphs have a direct translation into natural language." (Ivan Launders, "Socio-Technical Systems and Knowledge Representation", 2009)

"Conceptual graphs (CGs) and fuzzy logic are two logical formalisms that emphasize the target of natural language, each of which is focused on one of the two mentioned desired features of a logic for handling natural language. Conceptual graphs, based on semantic networks and Peirce's existential graphs, combine the visual advantage of graphical languages and the expressive power of logic." (Tru H Cao, "Conceptual Graphs and Fuzzy Logic: A Fusion for Representing and Reasoning with Linguistic Information", 2010)

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

"[...] scatterplots had advantages over earlier graphic forms: the ability to see clusters, patterns, trends, and relations in a cloud of points. Perhaps most importantly, it allowed the addition of visual annotations (point symbols, lines, curves, enclosing contours, etc.) to make those relationships more coherent and tell more nuanced stories." (Michael Friendly & Howard Wainer, "A History of Data Visualization and Graphic Communication", 2021)

"A tree-like structure or a tree diagram, one showing taxonomic (classification-related) relationships, is created. It is known as a dendrogram. It has branches pointing toward categories or classes. It is a pattern formed by a series of splits or segments of a given quantity of data over a set of compartments and the flow components. From this pattern, a description can be made of the profile of data allocation over the set of functional or structural compartments. The merger of clusters is terminated after every data point lies in one single cluster at the top of the tree." (Vinod K Khanna, "Introduction to Machine Learning Algorithms: Basic Principles and Mathematics", 2026)

"ML is a useful - and under-utilized - framework for studying LLMs. For one thing, LLMs are literally composed of simple ML algorithms (linear weighted averages and nonlinear transformations). Furthermore, using ML techniques like regression, classification, and clustering, can help reveal how concepts like grammar rules are represented inside LLMs. And finally, many people find LLMs to be intimidatingly complicated while finding ML to be much more approachable. Thus, using ML to study LLMs involves using simple tools to understand complicated tools." (Mike X Cohen,"50 ML Projects To Understand LLMs", 2026)

11 August 2026

🅽Mark Needham - Collected Quotes

"Adding graph features and context improves predictions, especially in situations where connections matter. [...] Unfortunately, many machine learning approaches today miss a lot of rich contextual information. This stems from ML’s reliance on input data built from tuples, leaving out a lot of predictive relationships and network data. Furthermore, contextual information is not always readily available or is too difficult to access and process. Even finding connections that are four or more hops away can be a challenge at scale for traditional methods. Using graphs, we can more easily reach and incorporate connected data." (Mark Needham & Amy E Hodler, "Graph Algorithms: Practical Examples in Apache Spark and Neo4j", 2019)

"At the most abstract level, graph analytics is applied to forecast behavior and prescribe action for dynamic groups. Doing this requires understanding the relationships and structure within the group. Graph algorithms accomplish this by examining the overall nature of networks through their connections. With this approach, you can understand the topology of connected systems and model their processes." (Mark Needham & Amy E Hodler, "Graph Algorithms: Practical Examples in Apache Spark and Neo4j", 2019)

"Community formation is common in all types of networks, and identifying them is essential for evaluating group behavior and emergent phenomena. The general principle in finding communities is that its members will have more relationships within the group than with nodes outside their group. Identifying these related sets reveals clusters of nodes, isolated groups, and network structure. This information helps infer similar behavior or preferences of peer groups, estimate resiliency, find nested relationships, and prepare data for other analyses. Community detection algorithms are also commonly used to produce network visualization for general inspection." (Mark Needham & Amy E Hodler, "Graph Algorithms: Practical Examples in Apache Spark and Neo4j", 2019)

"Feature extraction is a way to distill large volumes of data and attributes down to a set of representative descriptive attributes. The process derives numerical values (features) for distinctive characteristics or patterns in input data so that we can differentiate categories in other data. It’s used when data is difficult for a model to analyze directly - perhaps because of size, format, or the need for incidental comparisons. Feature selection is the process of determining the subset of extracted features that are most important or influential to a target goal. It’s used to surface predictive importance as well as for efficiency." (Mark Needham & Amy E Hodler, "Graph Algorithms: Practical Examples in Apache Spark and Neo4j", 2019)

"Graph algorithms provide one of the most potent approaches to analyzing connected data because their mathematical calculations are specifically built to operate on relationships. They describe steps to be taken to process a graph to discover its general qualities or specific quantities. Based on the mathematics of graph theory, graph algorithms use the relationships between nodes to infer the organization and dynamics of complex systems. Network scientists use these algorithms to uncover hidden infomation, test hypotheses, and make predictions about behavior." (Mark Needham & Amy E Hodler, "Graph Algorithms: Practical Examples in Apache Spark and Neo4j", 2019)

"Graph embedding is the representation of the nodes and relationships in a graph asfeature vectors. [...] Graph embedding uses graph data slightly differently than in connected feature extraction. It enables us to represent entire graphs, or subsets of graph data, in a numerical format ready for machine learning tasks. This is especially useful for unsupervised learning, where the data is not categorized because it pulls in more contextual information through relationships. Graph embedding is also useful for data exploration, computing similarity between entities, and reducing dimensionality to aid in statistical analysis." (Mark Needham & Amy E Hodler, "Graph Algorithms: Practical Examples in Apache Spark and Neo4j", 2019)

"In classic graph theory, an acyclic graph that is undirected is called a tree. In computer science, trees can also be directed. A more inclusive definition would be a graph where any two nodes are connected by only one path. Trees are significant for understanding graph structures and many algorithms. They play a key role in designing networks, data structures, and search optimizations to improve categorization or organizational hierarchies." (Mark Needham & Amy E Hodler, "Graph Algorithms: Practical Examples in Apache Spark and Neo4j", 2019)

"Machine learning is not artificial intelligence (AI), but a method for achieving AI. ML uses algorithms to train software through specific examples and progressive improvements based on expected outcome - without explicit programming of how to accomplish these better results. Training involves providing a lot of data to a model and enabling it to learn how to process and incorporate that information." (Mark Needham & Amy E Hodler, "Graph Algorithms: Practical Examples in Apache Spark and Neo4j", 2019)

"Make it a habit to run Connected Components to test whether a graph is connected as a preparatory step for general graph analysis. Performing this quick test can avoid accidentally running algorithms on only one disconnected component of a graph and getting incorrect results." (Mark Needham & Amy E Hodler, "Graph Algorithms: Practical Examples in Apache Spark and Neo4j", 2019)

"Putting together the right mix of features can increase accuracy because it fundamentally influences how our models learn. Because even modest improvements can make a significant difference [...]. Connected features are features extracted from the structure of the data. These features can be derived from graph-local queries based on parts of the graph surrounding a node, or graph-global queries that use graph algorithms to identify predictive elements within data based on relationships for connected feature extraction." (Mark Needham & Amy E Hodler, "Graph Algorithms: Practical Examples in Apache Spark and Neo4j", 2019)

"Using graphs for connected feature extraction can significantly improve our predictions. The ideal graph features and algorithms vary depending on the attributes of the data, including the network domain and graph shape. We suggest first considering the predictive elements within your data and testing hypotheses with different types of connected features before fine-tuning." (Mark Needham & Amy E Hodler, "Graph Algorithms: Practical Examples in Apache Spark and Neo4j", 2019)

"Without peripheral and related information, solutions that attempt to predict behavior or make recommendations for varying circumstances require more exhaustive training and prescriptive rules. This is partly why AI is good at specific, well-defined tasks, but struggles with ambiguity. Graph-enhanced ML can help fill in that missing contextual information that is so important for better decisions." (Mark Needham & Amy E Hodler, "Graph Algorithms: Practical Examples in Apache Spark and Neo4j", 2019)

22 July 2026

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

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

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

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

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

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

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

"These networks arise naturally in many diverse disciplines (such as biology, computer science, and social science), but all share the common characteristics of be- ing Inassive, sparse graphs with a power law degree distribution and small world structure. Such networks have now been coined scale-free, complex, self-organizing, or heterogeneous. Our own preferred term is self-organizing, since this is suggestive of the generative mechanisms underlying the network: over time, vertices choose their neighbour according to their own predisposition, rather than necessarily followil1g global rules." (Anthony Bonato, "A Course on the Web Graph", 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 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)

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

Quotable Mathematics

Pages