Hubbry Logo
logo
Network theory avatar
Network theory
Community hub

Network theory

logo
0 subscribers
Read side by side
Network theory
View on Wikipedia
from Wikipedia
A small example network with eight vertices (nodes) and ten edges (links)
Part of a series on
Network science
Internet_map_1024.jpg
Network types
Graphs
Features
Types
Models
Topology
Dynamics
  • Lists
  • Categories

In mathematics, computer science, and network science, network theory is a part of graph theory. It defines networks as graphs where the vertices or edges possess attributes. Network theory analyses these networks over the symmetric relations or asymmetric relations between their (discrete) components.

Network theory has applications in many disciplines, including statistical physics, particle physics, computer science, electrical engineering,[1][2] biology,[3] archaeology,[4] linguistics,[5][6][7] economics[8], finance, operations research, climatology, ecology, public health,[9][10][11] sociology,[12] psychology,[13] and neuroscience.[14][15][16] Applications of network theory include logistical networks, the World Wide Web, Internet, gene regulatory networks, metabolic networks, social networks, epistemological networks, etc.; see List of network theory topics for more examples.

Euler's solution of the Seven Bridges of Königsberg problem is considered to be the first true proof in the theory of networks.

Network optimization

[edit]

Network problems that involve finding an optimal way of doing something are studied as combinatorial optimization. Examples include network flow, shortest path problem, transport problem, transshipment problem, location problem, matching problem, assignment problem, packing problem, routing problem, critical path analysis, and program evaluation and review technique.

Network analysis

[edit]

Electric network analysis

[edit]

The analysis of electric power systems could be conducted using network theory from two main points of view:

  1. An abstract perspective (i.e., as a graph consists from nodes and edges), regardless of the electric power aspects (e.g., transmission line impedances). Most of these studies focus only on the abstract structure of the power grid using node degree distribution and betweenness distribution, which introduces substantial insight regarding the vulnerability assessment of the grid. Through these types of studies, the category of the grid structure could be identified from the complex network perspective (e.g., single-scale, scale-free). This classification might help the electric power system engineers in the planning stage or while upgrading the infrastructure (e.g., add a new transmission line) to maintain a proper redundancy level in the transmission system.[1]
  2. Weighted graphs that blend an abstract understanding of complex network theories and electric power systems properties.[2]

Social network analysis

[edit]
Visualization of social network analysis[17]

Social network analysis examines the structure of relationships between social entities.[18] These entities are often persons, but may also be groups, organizations, nation states, web sites, or scholarly publications.

Since the 1970s, the empirical study of networks has played a central role in social science, and many of the mathematical and statistical tools used for studying networks have been first developed in sociology.[19] Amongst many other applications, social network analysis has been used to understand the diffusion of innovations, news and rumors.[20] Similarly, it has been used to examine the spread of both diseases and health-related behaviors.[21] It has also been applied to the study of markets, where it has been used to examine the role of trust in exchange relationships and of social mechanisms in setting prices.[22] It has been used to study recruitment into political movements, armed groups, and other social organizations.[23] It has also been used to conceptualize scientific disagreements[24] as well as academic prestige.[25] More recently, network analysis (and its close cousin traffic analysis) has gained a significant use in military intelligence,[26] for uncovering insurgent networks of both hierarchical and leaderless nature.[citation needed]

Biological network analysis

[edit]
See also: Metabolic network, proteome, metabolome, and omics

With the recent explosion of publicly available high throughput biological data, the analysis of molecular networks has gained significant interest.[27] The type of analysis in this context is closely related to social network analysis, but often focusing on local patterns in the network. For example, network motifs are small subgraphs that are over-represented in the network. Similarly, activity motifs are patterns in the attributes of nodes and edges in the network that are over-represented given the network structure. Using networks to analyze patterns in biological systems, such as food-webs, allows us to visualize the nature and strength of interactions between species. The analysis of biological networks with respect to diseases has led to the development of the field of network medicine.[28] Recent examples of application of network theory in biology include applications to understanding the cell cycle[29] as well as a quantitative framework for developmental processes.[30]

Narrative network analysis

[edit]
Narrative network of US Elections 2012[31]

The automatic parsing of textual corpora has enabled the extraction of actors and their relational networks on a vast scale. The resulting narrative networks, which can contain thousands of nodes, are then analyzed by using tools from Network theory to identify the key actors, the key communities or parties, and general properties such as robustness or structural stability of the overall network, or centrality of certain nodes.[32] This automates the approach introduced by Quantitative Narrative Analysis,[33] whereby subject-verb-object triplets are identified with pairs of actors linked by an action, or pairs formed by actor-object.[31]

[edit]

Link analysis is a subset of network analysis, exploring associations between objects. An example may be examining the addresses of suspects and victims, the telephone numbers they have dialed, and financial transactions that they have partaken in during a given timeframe, and the familial relationships between these subjects as a part of police investigation. Link analysis here provides the crucial relationships and associations between very many objects of different types that are not apparent from isolated pieces of information. Computer-assisted or fully automatic computer-based link analysis is increasingly employed by banks and insurance agencies in fraud detection, by telecommunication operators in telecommunication network analysis, by medical sector in epidemiology and pharmacology, in law enforcement investigations, by search engines for relevance rating (and conversely by the spammers for spamdexing and by business owners for search engine optimization), and everywhere else where relationships between many objects have to be analyzed. Links are also derived from similarity of time behavior in both nodes. Examples include climate networks where the links between two locations (nodes) are determined, for example, by the similarity of the rainfall or temperature fluctuations in both sites.[34][35]

[edit]

Several Web search ranking algorithms use link-based centrality metrics, including Google's PageRank, Kleinberg's HITS algorithm, the CheiRank and TrustRank algorithms. Link analysis is also conducted in information science and communication science in order to understand and extract information from the structure of collections of web pages. For example, the analysis might be of the interlinking between politicians' websites or blogs. Another use is for classifying pages according to their mention in other pages.[36]

Centrality measures

[edit]

Information about the relative importance of nodes and edges in a graph can be obtained through centrality measures, widely used in disciplines like sociology. For example, eigenvector centrality uses the eigenvectors of the adjacency matrix corresponding to a network, to determine nodes that tend to be frequently visited. Formally established measures of centrality are degree centrality, closeness centrality, betweenness centrality, eigenvector centrality, subgraph centrality, and Katz centrality. The purpose or objective of analysis generally determines the type of centrality measure to be used. For example, if one is interested in dynamics on networks or the robustness of a network to node/link removal, often the dynamical importance[37] of a node is the most relevant centrality measure.

Assortative and disassortative mixing

[edit]
Further information: Assortative mixing

These concepts are used to characterize the linking preferences of hubs in a network. Hubs are nodes which have a large number of links. Some hubs tend to link to other hubs while others avoid connecting to hubs and prefer to connect to nodes with low connectivity. We say a hub is assortative when it tends to connect to other hubs. A disassortative hub avoids connecting to other hubs. If hubs have connections with the expected random probabilities, they are said to be neutral. There are three methods to quantify degree correlations.[38]

Recurrence networks

[edit]

The recurrence matrix of a recurrence plot can be considered as the adjacency matrix of an undirected and unweighted network. This allows for the analysis of time series by network measures. Applications range from detection of regime changes over characterizing dynamics to synchronization analysis.[39][40][41]

Spatial networks

[edit]

Many real networks are embedded in space. Examples include, transportation and other infrastructure networks, brain neural networks. Several models for spatial networks have been developed.[42]

Temporal networks

[edit]

Other networks emphasise the evolution over time of systems of nodes and their interconnections. Temporal networks are used for example to study how financial risk has spread across countries.[43] In this study, temporal networks are used to also visually trace the intricate dynamics of financial contagion during crises. Unlike traditional network approaches that aggregate or analyze static snapshots, the study uses a time-respecting path methodology to preserve the sequence and timing of financial crises contagion events. This enables the identification of nodes as sources, transmitters, or receivers of financial stress, avoiding mischaracterizations inherent in static or aggregated methods. Following this approach, banks are found to serve as key intermediaries in contagion paths, and temporal analysis pinpoints smaller countries like Greece and Italy as significant origins of shocks during crises—insights obscured by static approaches that overemphasize large economies like the US or Japan.

Temporal networks can also be used to explore how cooperation evolves in dynamic, real-world population structures where interactions are time-dependent.[44] Here the authors find that network temporality enhances cooperation compared to static networks, even though "bursty" interaction patterns typically hinder it. This finding also shows how cooperation and other emergent behaviours can thrive in realistic, time-varying population structures, challenging conventional assumptions rooted in static models.

In psychology, temporal networks enable the understanding of psychological disorders by framing them as dynamic systems of interconnected symptoms rather than outcomes of a single underlying cause. Using "nodes" to represent symptoms and "edges" to signify their direct interactions, symptoms like insomnia and fatigue are shown how they influence each other over time; also, disorders such as depression are shown not to be fixed entities but evolving networks, where identifying "bridge symptoms" like concentration difficulties can explain comorbidity between conditions such as depression and anxiety.[45]

Lastly, temporal networks enable a better understanding and controlling of the spread of infectious diseases.[46] Unlike traditional static networks, which assume continuous, unchanging connections, temporal networks account for the precise timing and duration of interactions between individuals. This dynamic approach reveals critical nuances, such as how diseases can spread via time-sensitive pathways that static models miss. Temporal data, such as interactions captured through Bluetooth sensors or in hospital wards, can improve predictions of outbreak speed and extent. Overlooking temporal correlations can lead to significant errors in estimating epidemic dynamics, emphasizing the need for a temporal framework to develop more accurate strategies for disease control.

Spread

[edit]

Content in a complex network can spread via two major methods: conserved spread and non-conserved spread.[47] In conserved spread, the total amount of content that enters a complex network remains constant as it passes through. The model of conserved spread can best be represented by a pitcher containing a fixed amount of water being poured into a series of funnels connected by tubes. Here, the pitcher represents the original source and the water is the content being spread. The funnels and connecting tubing represent the nodes and the connections between nodes, respectively. As the water passes from one funnel into another, the water disappears instantly from the funnel that was previously exposed to the water. In non-conserved spread, the amount of content changes as it enters and passes through a complex network. The model of non-conserved spread can best be represented by a continuously running faucet running through a series of funnels connected by tubes. Here, the amount of water from the original source is infinite. Also, any funnels that have been exposed to the water continue to experience the water even as it passes into successive funnels. The non-conserved model is the most suitable for explaining the transmission of most infectious diseases, neural excitation, information and rumors, etc.

Network immunization

[edit]

The question of how to immunize efficiently scale free networks which represent realistic networks such as the Internet and social networks has been studied extensively. One such strategy is to immunize the largest degree nodes, i.e., targeted (intentional) attacks[48] since for this case is relatively high and fewer nodes are needed to be immunized. However, in most realistic networks the global structure is not available and the largest degree nodes are unknown.

See also

[edit]

References

[edit]

Books

[edit]
  • Dorogovtsev SN, Mendes JR (2003). Evolution of Networks: from biological networks to the Internet and WWW. Oxford University Press. ISBN 978-0-19-851590-6.
  • Caldarelli G (2007). Scale-Free Networks. Oxford University Press. ISBN 978-0-19-921151-7.
  • Barrat A, Barthelemy M, Vespignani A (2008). Dynamical Processes on Complex Networks. Cambridge University Press. ISBN 978-0-521-87950-7.
  • Estrada E (2011). The Structure of Complex Networks: Theory and Applications. Oxford University Press. ISBN 978-0-199-59175-6.
  • Soramaki K, Cook S (2016). Network Theory and Financial Risk. Risk Books. ISBN 978-1-78272-219-9.
  • Latora V, Nicosia V, Russo G (2017). Complex Networks: Principles, Methods and Applications. Cambridge University Press. ISBN 978-1-107-10318-4.
[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Network theory

View on Grokipedia
from Grokipedia
Network theory, also referred to as network science, is an interdisciplinary field that studies the structure, dynamics, and function of complex systems represented as networks of nodes connected by edges, encompassing applications in mathematics, physics, computer science, social sciences, biology, and engineering.[1] At its core, it builds on graph theory, where nodes represent entities (such as individuals, neurons, or websites) and edges denote relationships or interactions (like friendships, synapses, or hyperlinks), enabling the modeling of real-world phenomena from social connections to electrical circuits and epidemic spreads.[2] The field emerged in the 18th century with Leonhard Euler's solution to the Königsberg bridge problem in 1736, which laid the foundations of graph theory as a mathematical framework for analyzing connectivity and paths in networks.[1] Key developments in the 20th century expanded network theory beyond pure mathematics; in the 1930s, sociologists like Jacob Moreno pioneered graph-based methods through sociometry to study social structures.[3] In the 1950s, these methods were further applied to examine influence and group dynamics, marking the birth of social network analysis.[1] The late 1990s saw a surge in interest driven by empirical studies of large-scale networks, such as the World Wide Web and biological systems, revealing universal patterns like small-world properties—where networks exhibit short average path lengths and high clustering, as modeled by Duncan Watts and Steven Strogatz in 1998—and scale-free topologies, characterized by power-law degree distributions due to preferential attachment, as proposed by Albert-László Barabási and Réka Albert in 1999.[4] These discoveries highlighted how network structure influences processes like information diffusion, disease propagation, and resilience to failures, with applications ranging from optimizing transportation systems to understanding neural connectivity in the brain.[4] Modern network theory integrates computational tools for analyzing massive datasets, employing metrics such as centrality (measuring node importance), modularity (detecting communities), and robustness (assessing failure tolerance), while addressing challenges like network evolution, multilayer structures, and dynamical processes on networks.[4] Influential works, including Mark Newman's comprehensive synthesis in 2010 and the interdisciplinary reviews by Katy Börner and colleagues in 2007, underscore its role in uncovering emergent behaviors in complex systems, bridging theoretical models with empirical data from diverse domains.[1][4]

History and Development

Origins in Graph Theory

Graph theory, the mathematical study of graphs as formal structures comprising vertices connected by edges, originated in the 18th century with foundational work on connectivity and traversal problems.[5] The discipline's inception is commonly traced to Leonhard Euler's 1736 solution to the Seven Bridges of Königsberg problem, which posed whether it was possible to traverse all seven bridges in the Prussian city of Königsberg (now Kaliningrad) exactly once and return to the starting point. Euler modeled the landmasses as vertices and the bridges as edges in a multigraph, proving that no such Eulerian cycle existed because exactly two vertices had odd degree, violating the necessary condition for an Eulerian circuit in a connected graph. This analysis established core concepts of graph traversal, paths, and connectivity, marking the first systematic application of graph-theoretic reasoning to a combinatorial problem.[6] In the 19th and early 20th centuries, graph theory expanded through contributions focused on enumeration and structural properties. Arthur Cayley advanced the field in 1857 by developing methods for enumerating trees, acyclic connected graphs, laying groundwork for counting distinct graph structures and their applications in chemical and combinatorial contexts. Later, Dénes Kőnig extended graph theory in 1931 with his work on matchings in bipartite graphs, proving the equivalence between the size of a maximum matching and a minimum vertex cover, which introduced duality principles pivotal to optimization in graphs.[7][8] By the mid-20th century, graph theory transitioned from abstract mathematics to applied domains, particularly in modeling social structures. Frank Harary's collaborations in the 1950s, notably the 1953 monograph with Robert Z. Norman, demonstrated graph theory's utility as a tool for analyzing social networks, balance in signed graphs, and group dynamics, bridging pure theory with interdisciplinary applications in sociology and psychology. This period saw graphs represented via adjacency matrices to facilitate computational analysis, though detailed formulations emerged later.

Key Contributors and Milestones

In the mid-20th century, Anatol Rapoport played a pivotal role in extending graph theory to the analysis of social structures, particularly during the 1940s and 1950s. Rapoport's work focused on modeling information diffusion and connectivity in populations, introducing concepts like biased nets to account for socio-structural preferences in interactions, which laid foundational ideas for probabilistic approaches in social network studies.[9][10] Sociologist Jacob L. Moreno also contributed significantly in the 1930s through sociometry, developing sociograms—graph representations of social relationships—to study group dynamics and interpersonal connections, establishing early empirical methods in social network analysis.[10] A major milestone came in 1959–1960 with the introduction of random graph models by Paul Erdős and Alfréd Rényi, which shifted network theory toward probabilistic methods by examining the evolution and properties of graphs generated randomly. Their seminal papers demonstrated thresholds for connectivity and component formation, providing mathematical tools to study large-scale networks beyond deterministic structures.[11][12] Stanley Milgram's 1967 small-world experiment further advanced the field by empirically investigating path lengths in social networks, revealing that individuals in the United States were typically connected through an average of six intermediaries, thus popularizing the "six degrees of separation" concept and inspiring subsequent research on network diameter.[13] In 1999, Albert-László Barabási and Réka Albert developed the theory of scale-free networks, proposing that many real-world networks exhibit power-law degree distributions arising from growth and preferential attachment mechanisms, where new nodes preferentially connect to highly connected ones. This model explained heterogeneous connectivity patterns observed in systems like the World Wide Web and biological networks.[14] Key organizational milestones included the formation of the International Network for Social Network Analysis (INSNA) in 1977 by Barry Wellman, which fostered interdisciplinary collaboration and standardized methodologies in the field.[15] Additionally, the 1990s saw the rise of computational tools such as Pajek, developed by Vladimir Batagelj and Andrej Mrvar, enabling efficient analysis and visualization of large networks with millions of vertices.[16]

Fundamental Concepts

Graphs and Networks

In graph theory, a graph is formally defined as an ordered triple $ G = (V(G), E(G), \psi_G) $, where $ V(G) $ is a nonempty finite set of vertices, $ E(G) $ is a set of edges disjoint from $ V(G) $, and $ \psi_G $ is an incidence function that associates each edge with an unordered pair of vertices (the ends of the edge).[17] This structure models pairwise relations between objects, with vertices representing entities and edges representing connections.[18] Graphs can be undirected, where edges have no direction, or directed, where edges are ordered pairs indicating orientation.[17] Networks extend this framework by applying graphs to real-world systems, often as labeled or weighted versions where vertices and edges carry attributes such as identities, capacities, or strengths to capture relational structures like social ties or physical interactions, rather than focusing solely on abstract combinatorial properties.[19] In this context, networks emphasize the modeling of complex systems in fields like sociology and physics, distinguishing them from pure mathematical graphs.[20] Key terminology includes simple graphs, which contain no loops (edges connecting a vertex to itself) or multiple edges between the same pair of vertices, and multigraphs, which permit multiple edges between vertices but typically exclude loops.[18] Two graphs are isomorphic if there exists a bijection between their vertex sets that preserves adjacency, meaning they share identical structural properties despite different labelings.[21] A graph is connected if there is a path—a sequence of adjacent edges—between every pair of distinct vertices.[21] The concept of networks gained prominence in the mid-20th century, particularly in sociology through structural balance theory, which used graphs to analyze interpersonal relations and group dynamics. In physics, random graph models introduced around the same period further popularized networks for studying emergent properties in large-scale systems.[11] This shift marked a departure from classical graph theory's combinatorial focus toward interdisciplinary applications in relational data.[19]

Nodes, Edges, and Basic Properties

In network theory, nodes, also referred to as vertices, serve as the basic building blocks representing discrete entities within a system, such as individuals in social networks or proteins in biological interaction networks.[22][23] These nodes encapsulate the primary objects of study and can carry attributes, such as labels identifying categories or states describing dynamic properties like activation levels.[24] For instance, in a social network, a node's label might denote gender, while in a neural network, its state could indicate firing activity.[25] Edges, alternatively called links, represent the connections or interactions between nodes, forming the structure that defines relational dependencies in the network.[26] Edges can be undirected, implying a symmetric relationship where traversal is possible in either direction, or directed, indicating an asymmetric interaction such as influence from one node to another in communication networks.[27] Additionally, edges may be unweighted, signifying only the existence of a tie without quantitative measure, or weighted, incorporating a numerical value to reflect the intensity, capacity, or frequency of the connection, as seen in transportation networks where weights denote travel times.[27] Certain network representations permit self-loops, edges that connect a node to itself to model reflexive processes like self-regulation in biological systems, and multiple edges between the same pair of nodes, allowing for multigraphs that capture parallel or repeated interactions.[27] For example, directed graphs, a common network type, emphasize the orientation of edges to model flows or hierarchies.[28] Basic properties of nodes and edges provide essential metrics for understanding local network structure. The degree of a node is defined as the total number of edges directly connected to it, serving as a primary indicator of a node's connectivity and influence within its immediate neighborhood.[29] In undirected networks, this count is straightforward, while in directed networks, it splits into in-degree (incoming edges) and out-degree (outgoing edges).[30] The clustering coefficient quantifies the local density of triangles around a node, calculated as the ratio of the number of actual triangles involving the node to the maximum possible triangles among its neighbors, thereby measuring the extent to which connected nodes tend to form closed triads.[31] Introduced by Watts and Strogatz, this property highlights tendencies toward local cohesion, with values ranging from 0 (no triangles) to 1 (fully connected neighborhood).[31] Path length refers to the shortest distance between two nodes, defined as the minimum number of edges required to traverse from one to the other along any connecting path.[32] This measure captures the efficiency of local reachability, distinguishing direct connections (length 1) from longer chains.[33] A key aggregate property is the average degree kˉ\bar{k}, which for undirected networks is computed as kˉ=2∣E∣∣V∣\bar{k} = \frac{2|E|}{|V|}, where ∣E∣|E| denotes the total number of edges and ∣V∣|V| the number of nodes; this formula reveals the overall connectivity density and is particularly useful for identifying sparse networks where kˉ\bar{k} remains far below the maximum possible value of ∣V∣−1|V| - 1.[34] Such sparsity is common in real-world networks, emphasizing efficient structures over dense ones.[34]

Network Types

Network theory encompasses a variety of network architectures that differ in the directionality, weighting, and structural organization of edges connecting nodes. These distinctions allow for modeling diverse relational systems, from symmetric social ties to asymmetric information flows. Undirected networks represent relations where connections are reciprocal, such as friendships in social groups, where the presence of an edge between two nodes implies mutual linkage without specified direction. In these networks, the adjacency matrix is symmetric, meaning that if node i is connected to node j, then node j is connected to node i, reflecting the bidirectional nature of the relation.[35][36] Directed networks, also known as digraphs, model asymmetric relations where edges have a specific orientation, such as citations in academic literature, where one paper references another but not vice versa. Here, each node has an in-degree, counting incoming edges, and an out-degree, counting outgoing edges, enabling analysis of influence flows or dependencies that undirected models cannot capture. This structure is essential for systems like communication networks or web links, where directionality conveys causality or hierarchy.[37][38] Weighted networks extend both undirected and directed forms by assigning numerical values to edges, representing the strength or intensity of connections, such as traffic volumes on transportation routes. These weights can quantify varying interaction levels, with higher values indicating stronger ties, and are often normalized— for instance, by dividing edge weights by the sum of weights incident to a node—to facilitate comparisons or probabilistic interpretations in analyses like random walks. Normalization methods, such as row normalization in adjacency matrices, ensure weights sum to unity per node, aiding in the computation of metrics like weighted degrees or strengths.[39] Beyond these core types, several specialized architectures address complex relational structures. Bipartite networks consist of two disjoint node sets, with edges connecting only between sets, such as collaborations between authors and publications, precluding intra-set connections and enabling projections onto unipartite graphs for further analysis. Multilayer networks incorporate multiple edge types or layers, each representing distinct interaction modes—like social and professional ties—allowing nodes to participate across layers with interlayer dependencies. Signed networks include positive and negative edges to model affinity or antagonism, as in trust-distrust relations, where balance theory posits structural stability when positive edges form clusters and negative edges span them.[40][41][42]

Mathematical Foundations

Matrix Representations

In network theory, matrix representations provide linear algebraic encodings of graph structures, enabling efficient computation and analysis of connectivity and paths. The adjacency matrix $ A $ of a graph with $ n $ vertices is an $ n \times n $ square matrix where the entry $ A_{ij} = 1 $ if there is an edge from vertex $ i $ to vertex $ j $, and $ A_{ij} = 0 $ otherwise.[43] For undirected networks, where edges lack direction, the adjacency matrix is symmetric, satisfying $ A = A^T $, because an edge between $ i $ and $ j $ implies the same for $ j $ and $ i $.[43] In directed networks, the matrix is generally asymmetric, reflecting the orientation of edges.[43] The incidence matrix $ B $ offers an alternative encoding, with rows corresponding to the $ n $ vertices and columns to the $ m $ edges. Each entry $ B_{ve} = 1 $ if vertex $ v $ is incident to edge $ e $, and 0 otherwise, capturing vertex-edge incidences without orientation.[44] This unoriented form is particularly useful in flow problems, such as modeling commodity flows across edges while respecting vertex capacities.[44] A key property is that the product $ B B^T $ yields a matrix whose diagonal entries are the degrees of the vertices (forming the degree matrix $ D $) and off-diagonal entries indicate shared incidences, resulting in $ B B^T = D + A $ for simple undirected graphs without multiple edges.[45] The Laplacian matrix $ L $, defined as $ L = D - A $, combines the degree matrix $ D $ (a diagonal matrix with vertex degrees on the diagonal) and the adjacency matrix to encode diffusion-like processes on the network.[46] The eigenvalues of $ L $ provide insights into network connectivity; specifically, the second smallest eigenvalue, known as the algebraic connectivity or Fiedler value, quantifies the graph's robustness to disconnection, with higher values indicating better overall connectivity.[47] A graph is connected if and only if this eigenvalue is positive.[47] Powers of the adjacency matrix reveal path structures: the entry $ (A^k)_{ij} $ counts the number of walks of length $ k $ from vertex $ i $ to vertex $ j $, derived from the matrix multiplication rule where each step corresponds to an edge traversal.[43] This property stems from the fact that multiplying $ A $ by itself accumulates adjacency relations over multiple steps, enabling the enumeration of closed walks (when $ i = j $) or open paths in acyclic cases.[43]

Degree Distributions and Motifs

In network theory, the degree distribution $ P(k) $ represents the probability that a randomly selected node has degree $ k $, where degree denotes the number of edges connected to the node.[48] This distribution provides a fundamental statistical description of connectivity patterns, capturing how connections are unevenly spread across nodes. Empirically, $ P(k) $ is fitted by constructing histograms from the degree sequence of all nodes in the observed network, allowing researchers to identify underlying forms such as exponential or power-law tails.[49] In scale-free networks, like those modeling the internet or protein interactions, $ P(k) $ follows a power-law $ P(k) \sim k^{-\gamma} $ with $ 2 < \gamma < 3 $, resulting in a few highly connected hub nodes that dominate the network's structure and influence its robustness to failures. Network motifs extend this analysis to local substructures, defined as small induced subgraphs of 3 to 5 nodes that recur at frequencies significantly higher than in randomized null models. These patterns, such as triads or directed loops, reveal building blocks of network architecture that may underpin functional properties. Detection involves subgraph enumeration algorithms that systematically identify all possible small subgraphs and count their occurrences; a widely used tool is mfinder, which employs edge-coloring techniques for efficient sampling in large networks.[50] Significance is tested by generating an ensemble of randomized networks—typically preserving the original degree distribution and edge density—and computing z-scores or p-values for motif frequencies, ensuring deviations are not due to global constraints. Hub nodes from power-law degree distributions exemplify how local connectivity statistics enable global phenomena, such as efficient information flow in transportation networks. In biological systems, the feed-forward loop (FFL) motif—a triad where one node regulates both a second node and a target, with the second also regulating the target—appears enriched in gene regulatory networks.[51] Coherent FFLs, with consistent regulatory signs, promote signal coherence by accelerating responses to persistent inputs while delaying transient ones, thus filtering noise and enhancing decision-making in processes like bacterial chemotaxis.[51]

Characteristic Network Models

Characteristic network models provide foundational frameworks for understanding the structural properties of networks by generating synthetic graphs that mimic observed empirical features. These models emphasize generative processes that produce specific degree distributions and topological characteristics, enabling theoretical analysis of network behavior. The Erdős–Rényi model, denoted as G(n, p), constructs a random graph with n nodes where each possible edge is included independently with probability p. In this model, the degree of a node follows a binomial distribution Bin(n-1, p), leading to a relatively uniform degree distribution across nodes. A key property is the phase transition at the percolation threshold p = 1/n, where a giant connected component emerges, marking the shift from fragmented to cohesive network structure.[12] The small-world network model, introduced by Watts and Strogatz, starts with a regular lattice and rewires a fraction of edges randomly to create intermediate structures between order and randomness. This rewiring preserves high clustering coefficients typical of lattices while drastically reducing average path lengths, resulting in networks that are both locally dense and globally efficient. The model's small-world regime is quantified by the clustering ratio γ=Creal/Crand\gamma = C_{\text{real}} / C_{\text{rand}} (close to 1 for high clustering) and the path length ratio λ=Lreal/Lrand\lambda = L_{\text{real}} / L_{\text{rand}} (close to 1 for short paths), where CC and LL denote clustering coefficient and average path length, respectively, compared to random graph equivalents.[52] Scale-free networks, as proposed by Barabási and Albert, emerge through a generative process involving continuous growth (adding new nodes over time) and preferential attachment (new nodes connect to existing nodes with probability proportional to their degree). This mechanism yields a power-law degree distribution P(k)∼k−γP(k) \sim k^{-\gamma}, where γ\gamma typically ranges from 2 to 3, characterized by a few highly connected hubs and many low-degree nodes, capturing the heterogeneity observed in many real-world systems.[53] In comparison, the Erdős–Rényi model emphasizes uniformity with homogeneous degrees and sharp transitions, suitable for studying baseline random connectivity; the small-world model balances local clustering with global reach for efficient information propagation; and scale-free models highlight heterogeneity and robustness through hubs, each addressing distinct empirical network motifs without overlapping generative assumptions.[12][52][53]

Static Network Analysis

Centrality Measures

Centrality measures in network theory quantify the importance or influence of nodes based on their structural positions within a graph. These metrics help identify key actors in social, biological, or technological networks by evaluating factors such as connectivity, proximity, and mediation roles. Developed primarily in the context of social network analysis, centrality measures provide insights into how nodes facilitate information flow, resource distribution, or control in a system. Degree centrality is the simplest measure, defined as the normalized number of direct connections a node has to others in the network. For a node vv in a graph with nn nodes, it is given by CD(v)=kv/(n−1)C_D(v) = k_v / (n-1), where kvk_v is the degree of vv. This metric assumes that a node's influence is proportional to its immediate connections, making it computationally efficient for large networks but limited in capturing indirect influences. Betweenness centrality assesses a node's role as an intermediary on shortest paths between other nodes, highlighting its potential to control communication or flow. It is formalized as CB(v)=∑s≠t≠vσst(v)/σstC_B(v) = \sum_{s \neq t \neq v} \sigma_{st}(v) / \sigma_{st}, where σst\sigma_{st} is the total number of shortest paths from node ss to tt, and σst(v)\sigma_{st}(v) is the number of those paths passing through vv. The naive computation requires evaluating all pairs of nodes, leading to O(n3)O(n^3) time complexity, but Brandes' algorithm improves this to O(nm)O(nm) for sparse graphs with mm edges by using breadth-first search and dependency accumulation.[54] Closeness centrality evaluates a node's efficiency in reaching all others, based on its average distance to the rest of the network. It is defined as CC(v)=1/∑ud(v,u)C_C(v) = 1 / \sum_u d(v,u), where d(v,u)d(v,u) is the shortest-path distance between vv and uu. This measure, originally motivated by communication efficiency in group tasks, favors nodes that minimize the total path length to others, though it assumes a connected graph and can be sensitive to disconnected components.[55] Eigenvector centrality extends degree centrality by accounting for the centrality of a node's neighbors, positing that connections to influential nodes enhance a node's own importance. It satisfies the equation CE(v)=1λ∑uAvuCE(u)C_E(v) = \frac{1}{\lambda} \sum_u A_{vu} C_E(u), where AA is the adjacency matrix and λ\lambda is the largest eigenvalue; the solution is the principal eigenvector of AA. This recursive definition, solved via power iteration, captures global network structure but requires the graph to be strongly connected for convergence. A damped variant, PageRank, incorporates a teleportation probability to address issues like dangling nodes and sinks, defined as CPR(v)=1−dN+d∑uAvuCPR(u)kuC_{PR}(v) = \frac{1-d}{N} + d \sum_u \frac{A_{vu} C_{PR}(u)}{k_u}, where dd is the damping factor (typically 0.85) and NN is the number of nodes; it was pivotal in web search ranking.[56][57] Despite their utility, centrality measures exhibit limitations, particularly in scalability for large networks where exact computation becomes prohibitive due to high time complexity. For instance, betweenness and closeness require all-pairs shortest paths, which is infeasible for graphs with millions of nodes, prompting approximations via sampling or heuristics that trade accuracy for speed. These measures are also sensitive to network size and density, potentially overemphasizing local structure in sparse graphs.[58][59]

Assortative Mixing Patterns

Assortative mixing patterns in networks refer to the tendency for nodes to connect preferentially to others with similar or dissimilar attributes, most commonly analyzed through node degrees. This phenomenon influences network structure and dynamics, particularly how high-degree nodes (hubs) link to one another. In assortative mixing, hubs connect to other hubs, promoting clustering among similar nodes, while in disassortative mixing, hubs link to low-degree nodes, creating a more hierarchical structure. These patterns are quantified using the assortativity coefficient, which measures the correlation in degrees at the ends of edges.[60] The assortativity coefficient $ r $ is defined as the Pearson correlation coefficient of the degrees of nodes connected by edges:
r=∑jkjk(ejk−qjqk)σq2 r = \frac{\sum_{jk} jk (e_{jk} - q_j q_k)}{\sigma_q^2}
where $ e_{jk} $ is the joint probability distribution of degrees $ j $ and $ k $ at the ends of edges, $ q_k = \frac{(k+1) p_{k+1}}{\langle k \rangle} $ is the excess degree distribution (with $ p_k $ the degree distribution and $ \langle k \rangle $ the average degree), and $ \sigma_q^2 $ is the variance of $ q_k $. Values of $ r $ range from -1 to 1; positive $ r $ indicates assortative mixing (e.g., $ r > 0 $), where similar degrees correlate positively, and negative $ r $ indicates disassortative mixing (e.g., $ r < 0 $), where high-degree nodes connect to low-degree ones. Neutral mixing occurs near $ r = 0 $, resembling random connections. This measure relies on the underlying degree distribution but focuses specifically on pairwise correlations between connected nodes.[60][61] The degree mixing matrix, represented by the empirical distribution $ e_{jk} $, captures these correlations by showing the fraction of edges between nodes of degrees $ j $ and $ k $. Diagonal elements in $ e_{jk} $ (where $ j \approx k $) dominate in assortative networks, reflecting homophily by degree, while off-diagonal elements (high $ j $, low $ k $) prevail in disassortative cases. This matrix is constructed from observed edges and compared to the null model $ q_j q_k $ to detect deviations from randomness. In practice, $ e_{jk} $ reveals degree correlations empirically, aiding visualization and further analysis of mixing beyond the scalar $ r $.[61] Assortative mixing patterns have significant implications for network robustness and function. Assortative networks, with positive $ r $, exhibit greater resilience to random vertex removal because hubs reinforce each other, maintaining connectivity; for instance, removing vertices disrupts percolation less severely than in disassortative networks. Conversely, disassortative networks, with negative $ r ,aremorevulnerabletotargetedattacksonhubsbutmayenhanceinformationflowfromhubstoperipherals.Real−worldexamplesillustratethesepatterns:socialnetworkslikephysicscoauthorshipgraphsshowstrongassortativity(, are more vulnerable to targeted attacks on hubs but may enhance information flow from hubs to peripherals. Real-world examples illustrate these patterns: social networks like physics coauthorship graphs show strong assortativity ( r = 0.363 ),wherecollaboratorstendtohavesimilarconnectivity,whiletechnologicalnetworksliketheinternetdisplaydisassortativity(), where collaborators tend to have similar connectivity, while technological networks like the internet display disassortativity ( r = -0.189 ),withhigh−degreerouterslinkingtomanylow−degreehosts;biologicalnetworks,suchasproteininteractions,alsotendtowarddisassortativity(), with high-degree routers linking to many low-degree hosts; biological networks, such as protein interactions, also tend toward disassortativity ( r = -0.156 $), facilitating diverse interactions. These differences underscore how mixing shapes network evolution and stability across domains.[60][61]

Community Detection

Community detection in network theory involves identifying groups of nodes that are more densely connected internally than to the rest of the network, revealing modular structures that often correspond to functional units in real-world systems. These communities can enhance understanding of network organization, such as social circles in friendship networks or protein complexes in biological networks. Methods for community detection typically aim to partition the graph into subgraphs that maximize intra-community ties while minimizing inter-community connections, addressing the challenge of scalability in large, sparse networks. One prominent approach is modularity optimization, which quantifies the strength of community divisions by comparing the observed density of edges within communities to what would be expected in a random network with the same degree sequence. The modularity $ Q $ is defined as
Q=12m∑ij[Aij−kikj2m]δ(ci,cj), Q = \frac{1}{2m} \sum_{ij} \left[ A_{ij} - \frac{k_i k_j}{2m} \right] \delta(c_i, c_j),
where $ A_{ij} $ is the adjacency matrix element between nodes $ i $ and $ j $, $ k_i $ and $ k_j $ are the degrees of nodes $ i $ and $ j $, $ m $ is the total number of edges, and $ \delta(c_i, c_j) $ is 1 if nodes $ i $ and $ j $ are in the same community and 0 otherwise.[62] This measure, introduced by Newman and Girvan, favors partitions where $ Q $ is maximized, typically approaching 1 for strong community structures and near 0 for random graphs.[62] The Louvain algorithm efficiently optimizes modularity through a hierarchical greedy procedure: it first assigns nodes to communities based on local modularity gains, then aggregates communities into supernodes, and repeats until convergence, achieving near-linear time complexity for large networks.[63] Spectral partitioning methods leverage the eigenvalues and eigenvectors of the graph Laplacian matrix to identify natural cuts in the network. The Laplacian $ L = D - A $, where $ D $ is the degree matrix and $ A $ the adjacency matrix, has eigenvectors whose components indicate node separations; the second smallest eigenvector (Fiedler vector) often bisects the graph into communities by assigning nodes based on sign changes.[64] For multi-way partitions, higher-order eigenvectors are used in k-means clustering on the spectral embedding. Normalized cut minimization extends this by balancing cut size against community volumes, solving the relaxed optimization $ \min \frac{\text{cut}(A,B)}{vol(A)} + \frac{\text{cut}(A,B)}{vol(B)} $ via the second eigenvector of the normalized Laplacian, which penalizes unbalanced partitions and improves detection in heterogeneous networks.[64] Overlapping communities, where nodes belong to multiple groups, are detected using methods like clique percolation, which identifies k-cliques (complete subgraphs of k nodes) and links those sharing $ k-1 $ nodes to form percolating communities, capturing soft boundaries in dense regions such as collaboration networks. Fuzzy clustering approaches assign nodes partial memberships to communities, often by optimizing a fuzzy modularity or similarity-based objective, allowing probabilistic overlaps that reflect multifaceted roles, as in author disambiguation tasks. However, these methods face resolution limits in hierarchical or multi-scale structures, where modularity-based techniques fail to resolve small communities below a size threshold proportional to the square root of network size, merging them into larger ones despite distinct internal densities.[65] Evaluating community detection involves comparing detected partitions to ground-truth labels using normalized mutual information (NMI), which measures the mutual information between partitions normalized by the average entropy of each, yielding values from 0 (independent) to 1 (identical).[66] NMI is robust to varying community sizes but assumes discrete assignments, posing challenges for overlapping cases; resolution limits further complicate assessment, as algorithms may overlook fine-grained structures in favor of coarser ones, impacting applications requiring precise modularity.[66][65]

Applications in Social Systems

Social Network Analysis

Social network analysis (SNA) applies network theory to examine the structure and dynamics of human relationships, modeling social systems as graphs where nodes represent actors such as individuals or groups, and edges denote ties like friendships, collaborations, or communications. This approach emphasizes how positions— the specific locations of actors within the network— and roles— the recurring patterns of ties actors exhibit— influence behavior, information flow, and social influence. By quantifying relational patterns, SNA reveals underlying social mechanisms beyond individual attributes, such as how ties facilitate resource access or constrain opportunities.[67] A fundamental distinction in SNA lies between ego networks and whole networks. Ego networks center on a focal actor (the ego) and their direct connections (alters), capturing local structures like support circles or personal influence spheres without requiring data on the broader population; this method is efficient for large-scale surveys but limits insights into global patterns. In contrast, whole networks encompass all actors and ties within a bounded population, such as a workplace or community, enabling analysis of collective properties like cohesion or fragmentation, though data collection is more resource-intensive.[67][68] Key metrics in SNA include density and reciprocity, which assess network cohesion. Density is the ratio of observed ties to the maximum possible ties, reflecting how interconnected a social group is; low density may indicate sparse relations conducive to innovation spread, while high density suggests tight-knit communities with redundant information. Reciprocity measures the mutuality of directed ties, calculated as the proportion of dyads where both actors connect to each other, often signaling trust or balanced exchanges in relationships like alliances or conversations. Another pivotal metric is structural holes, gaps between non-adjacent actors that create brokerage advantages; actors spanning these holes gain control over information flows and novel opportunities, as theorized by Burt (1992).[67][69][70] To model tie formation statistically, building on the exponential family of probability distributions for directed graphs introduced by Holland and Leinhardt (1981)[71], Frank and Strauss (1986) developed Markov random graph models, providing a framework for exponential random graph models (ERGMs) that treat observed networks as realizations from a probability distribution conditioned on network statistics like triad closures or degree distributions. ERGMs estimate parameters that explain why ties exist, accounting for dependencies such as homophily or transitivity, and are widely used to test hypotheses about social processes in empirical data.[72] SNA has illuminated processes like the diffusion of innovations, where Granovetter's (1973) strength of weak ties argument demonstrates that loose acquaintances bridge dense clusters, accelerating the spread of ideas or behaviors across diverse groups more effectively than strong ties within them. In online social networks, such as Facebook, analyses reveal similar patterns: users form dense ego networks of close friends but rely on weak ties for broader reach, with community detection uncovering hierarchical structures of overlapping groups that influence content virality and user engagement. Centrality measures in these contexts identify key influencers, as detailed in broader static analysis sections.[73][74]

Link Analysis

Link analysis encompasses computational techniques that derive insights from the structure and semantics of links in relational data, particularly in directed graphs representing hyperlinks, citations, or transactions. These methods leverage the topology of connections to infer importance, relevance, or irregularities, with foundational applications in web search and information retrieval. By modeling networks where nodes represent entities like web pages or documents and edges denote relationships such as incoming links, link analysis quantifies authority and influence through iterative scoring mechanisms. The Hyperlink-Induced Topic Search (HITS) algorithm, introduced by Jon Kleinberg, identifies hubs and authorities within a web graph by assigning scores based on mutual reinforcement. In this approach, a hub score measures a page's value in pointing to high-quality authorities, while an authority score reflects the quality of pages linking to it; these scores are computed iteratively using adjacency matrices until convergence, treating the problem as finding principal eigenvectors of the hub-authority product matrix. HITS operates on a focused subgraph derived from a query, expanding to nearby pages to mitigate noise from the broader web. This method has been influential in topic-specific ranking, though it is susceptible to spam through link farms. PageRank, developed by Sergey Brin and Larry Page, provides a global measure of page importance by simulating a random surfer model on the web graph. The score for node ii is given by
PR(i)=1−dn+d∑j→iPR(j)kj, PR(i) = \frac{1-d}{n} + d \sum_{j \to i} \frac{PR(j)}{k_j},
where nn is the number of nodes, dd (typically 0.85) is the damping factor accounting for random jumps to avoid trapped surfers, and kjk_j is the out-degree of node jj. This equation is solved iteratively as a system of linear equations, yielding a stationary distribution that ranks pages by their likelihood of being visited. PageRank's robustness to local manipulations stems from its incorporation of global structure, powering early Google search results.[75] In web link analysis, co-citation and bibliographic coupling extend these ideas to assess document similarity via shared connections. Co-citation occurs when two documents are jointly cited by a third, indicating topical relatedness; the frequency of such overlaps forms a similarity matrix for clustering or ranking in search engines. Introduced by Henry Small, this measure has been applied to map scientific fields and enhance recommendation systems by propagating relevance through citation graphs. Conversely, bibliographic coupling, pioneered by Melvin M. Kessler, links documents that cite common references, capturing forward-looking affinities useful for predicting research trends and improving query expansion in information retrieval. Both techniques underpin modern applications like personalized search and content suggestion on platforms such as academic databases.[76] Beyond the web, link analysis informs broader domains like co-authorship networks, where edges represent joint publications among researchers. Mark Newman's analysis revealed these networks exhibit small-world properties, with power-law degree distributions and high clustering, enabling the identification of influential scientists through centrality-like metrics derived from collaboration links. In transaction graphs, such as financial or communication records, link analysis detects anomalies by flagging unusual patterns like isolated high-value transfers or dense subgraphs indicative of fraud. Leman Akoglu and colleagues surveyed graph-based methods that score nodes or edges for deviation from expected neighborhoods, achieving high precision in real-world datasets for applications in cybersecurity and banking oversight.[77][78]

Applications in Physical and Biological Systems

Electrical Network Analysis

Electrical network analysis applies graph-theoretic principles from network theory to model and solve problems in electrical circuits and systems, treating components like resistors, capacitors, and inductors as edges connecting nodes (junctions). This approach enables the representation of complex circuits as graphs, where vertices correspond to nodes and edges to circuit elements, facilitating the use of linear algebra and combinatorial optimization for analysis. By framing electrical flows as processes on networks, engineers can predict behaviors such as current distribution, voltage drops, and signal propagation, which is essential for designing reliable power systems and integrated circuits. Kirchhoff's laws serve as fundamental network constraints in this framework, expressed through the graph's incidence matrix. The incidence matrix $ \mathbf{A} $ of a directed graph with $ n $ nodes and $ m $ edges is an $ n \times m $ matrix where each column corresponds to an edge, with entries $ +1 $ at the row of the "from" node, $ -1 $ at the "to" node, and 0 elsewhere; this matrix encodes the topology for applying Kirchhoff's current law (KCL) and voltage law (KVL). KCL states that the algebraic sum of currents entering a node is zero, which translates to $ \mathbf{A} \mathbf{i} = 0 $ for current vector $ \mathbf{i} $, ensuring conservation of charge across the network. Similarly, KVL asserts that the algebraic sum of voltages around any closed loop is zero, represented as $ \mathbf{B} \mathbf{v} = 0 $, where $ \mathbf{B} $ is the loop matrix derived from the incidence matrix's null space, and $ \mathbf{v} $ is the voltage vector across edges. These matrix formulations allow systematic enforcement of physical laws in large-scale circuit simulations. Impedance and admittance matrices provide algebraic tools for solving linear electrical networks under steady-state conditions. The admittance matrix, or Y-matrix, relates node voltages to injected currents via $ \mathbf{i} = \mathbf{Y} \mathbf{v} $, where diagonal elements represent the sum of admittances connected to a node, and off-diagonals are negative sums of admittances between nodes. In power systems, the Y-bus matrix is a specialized form of the admittance matrix, constructed from line impedances and shunt elements to model bus interconnections in transmission grids. To solve for unknown voltages or currents, Gaussian elimination is applied to the Y-matrix equations, reducing the system to triangular form for efficient back-substitution, particularly useful in sparse networks where only a few non-zero entries exist due to localized connections. This method scales well for large power networks, enabling load flow analysis without explicit loop identification. Graph-theoretic tools extend these analyses by optimizing circuit layouts and performance. Minimum spanning trees (MSTs) are used for wiring optimization in electrical networks, selecting a subset of edges that connects all nodes with minimal total impedance or cost, as in printed circuit board routing where Kruskal's or Prim's algorithms minimize wire length while avoiding cycles. Shortest paths algorithms, such as Dijkstra's, model signal delay by treating edge weights as propagation times or resistances, identifying the minimal-delay route between components in integrated circuits. These combinatorial approaches integrate seamlessly with electrical constraints, enhancing design efficiency in high-density layouts. In VLSI design, network theory aids in managing interconnect delays and power distribution across millions of transistors modeled as graphs, where centrality measures help prioritize critical paths to reduce latency. For power grid stability, spectral graph theory analyzes eigenvalue distributions of the Laplacian matrix (derived from the incidence matrix) to assess vulnerability to cascading failures, as demonstrated in models of blackout propagation. Additionally, Fourier analysis on graphs extends classical signal processing to irregular electrical networks, decomposing voltages or currents into eigenbasis of the graph Laplacian for frequency-domain responses, useful in filtering noise in sensor networks or harmonic analysis in AC circuits.

Biological Network Analysis

Biological network analysis applies graph theory to model and interpret interactions within living systems, ranging from molecular to ecological scales. These networks capture the interconnected nature of biological processes, revealing emergent properties such as robustness and modularity that underpin cellular function and organismal adaptation. Key types include protein-protein interaction (PPI) networks, metabolic networks, and neural networks, each exhibiting distinct topological features that reflect evolutionary pressures and functional constraints.[79] PPI networks represent physical or functional associations between proteins, often displaying scale-free degree distributions where a few highly connected hubs interact with many partners. This topology arises from evolutionary mechanisms like gene duplication followed by divergence, where duplicated genes retain some interactions while accumulating new ones, leading to power-law distributions observed across species from yeast to humans.[79] Metabolic networks map enzymatic reactions converting substrates to products, typically showing bow-tie structures with broad input and output funnels for efficient resource utilization. Neural networks, or connectomes, depict synaptic connections between neurons, characterized by small-world properties that balance local clustering and global efficiency for rapid information processing.[80][81] Analysis of these networks highlights robustness to random failures, attributed to heterogeneous degree distributions where most nodes have low connectivity, allowing the system to tolerate perturbations without collapse. In PPI networks, highly connected hub proteins are often essential, as their removal leads to lethality, underscoring the correlation between centrality and functional importance. Synthetic lethality emerges in gene regulatory networks when pairwise gene disruptions cause cell death despite individual viability, often due to redundant pathways; this phenomenon is exploited in cancer therapies targeting vulnerabilities in mutated cells. Scale-free motifs, such as recurrent subgraphs, further contribute to evolutionary stability by facilitating adaptive rewiring.[82][83] Methods for analyzing biological networks include flux balance analysis (FBA) for metabolic pathways, which optimizes steady-state fluxes under stoichiometric constraints to predict growth rates and metabolite flows without kinetic details. For gene regulation dynamics, Boolean networks model gene states as binary (on/off) with logical rules, simulating attractor states that represent stable phenotypes like cell differentiation. These approaches reveal how network topology influences dynamical behaviors, such as oscillatory patterns in regulatory circuits.[80][84] Examples abound in ecological and neural contexts. Food webs, modeling predator-prey interactions, often exhibit disassortative mixing by degree, where high-degree species (e.g., basal producers) preferentially connect to low-degree species, which can enhance stability against species loss.[85] Brain connectomes, such as those from the human or Drosophila, demonstrate modular organization with rich-club hubs integrating sensory-motor functions.[81] Evolutionary models like duplication-divergence simulate PPI network growth, reproducing observed scale-free properties and predicting interaction retention probabilities around 0.3–0.4 for realism.[86]

Dynamic and Spatiotemporal Networks

Temporal Networks

Temporal networks, also known as time-varying or dynamic networks, represent systems where the presence or absence of connections between nodes evolves over time, contrasting with static networks that assume fixed topologies. These networks are formalized through representations such as time-stamped contact sequences, denoted as triples (i,j,t)(i, j, t) indicating an edge between nodes ii and jj at time tt, or as discrete snapshots of the adjacency matrix A(t)A(t) at successive intervals. This temporal structure captures real-world phenomena like human interactions or transportation flows, where links are intermittent rather than persistent. A key distinction from static networks lies in the concept of temporal paths, or time-respecting walks, which require that the sequence of edge timestamps is non-decreasing (t1≤t2≤⋯≤tkt_1 \leq t_2 \leq \cdots \leq t_k) to ensure causality in information or influence propagation. Unlike shortest paths in static graphs, temporal paths prioritize arrival time over mere hop count, often computed via efficient algorithms that aggregate over time windows to assess reachability. This framework highlights how temporal ordering can dramatically alter network efficiency; for instance, in empirical datasets like mobile phone calls, the fraction of reachable node pairs via time-respecting paths can be orders of magnitude lower than in the static projection. Metrics for temporal networks extend static centrality measures to account for time. Temporal betweenness centrality quantifies a node's role in facilitating time-respecting paths between all pairs, defined as CBS(v)=∑s≠v≠tσst(v)σstC_B^S(v) = \sum_{s \neq v \neq t} \frac{\sigma_{st}(v)}{\sigma_{st}}, where σst\sigma_{st} is the number of time-respecting paths from ss to tt, and σst(v)\sigma_{st}(v) passes through vv. This metric, applied to datasets such as email communications, reveals time-dependent bottlenecks not visible in aggregated graphs. Another important property is burstiness, characterizing the irregular timing of contacts through the inter-event time distribution, often following a power-law P(τ)∼τ−(α+1)P(\tau) \sim \tau^{-(\alpha+1)} with α≈1\alpha \approx 1, leading to a burstiness coefficient B=στ−μτστ+μτB = \frac{\sigma_\tau - \mu_\tau}{\sigma_\tau + \mu_\tau} where στ\sigma_\tau and μτ\mu_\tau are the standard deviation and mean of inter-event times. In contact sequences from proximity sensors, high burstiness (B>0.5B > 0.5) indicates clustered interactions, slowing diffusion compared to Poissonian processes. Models of temporal networks aim to replicate these empirical features. Time-respecting walks form the basis for analyzing dynamical processes, enforcing chronological order in path traversal, which is essential for simulating realistic spreading without hindsight. A prominent generative model is the activity-driven network, where each node ii has an intrinsic activity potential xix_i drawn from a distribution (e.g., power-law), generating mm outgoing edges to randomly selected nodes at each discrete time step Δt\Delta t, with edges decaying after a persistence time.[87] This approach naturally produces bursty degree sequences and heterogeneous connectivity without preferential attachment, matching observations in online messaging data where active users drive transient hubs.[87] Applications of temporal networks are prominent in modeling epidemic spread on dynamic contacts. In susceptible-infected (SI) models over time-varying graphs, burstiness and temporal correlations increase outbreak thresholds; for example, simulations on empirical face-to-face interaction data show that ignoring timing overestimates spread by up to 50%. Activity-driven models further reveal that the epidemic threshold for SIS processes is λc/μ=⟨x⟩/⟨x2⟩\lambda_c / \mu = \langle x \rangle / \langle x^2 \rangle, where λ\lambda and μ\mu are infection and recovery rates, emphasizing the role of activity heterogeneity in containment strategies.[87] For evolving social ties, temporal representations track tie reinforcement over repeated contacts, as in weighted temporal graphs where edge weights accumulate based on interaction frequency, applied to collaboration networks to predict community evolution and influence diffusion.

Spatial Networks

Spatial networks are graphs where nodes are embedded in a physical space, such as Euclidean geometry, and the formation of edges is influenced by the spatial positions of the nodes. In these networks, the probability of an edge between two nodes typically decreases with their Euclidean distance, reflecting constraints like cost or physical feasibility. For instance, connection probabilities often follow a power-law decay, pij∝dE(i,j)−αp_{ij} \propto d_E(i,j)^{-\alpha}, where dE(i,j)d_E(i,j) is the Euclidean distance and α≈3\alpha \approx 3 for long-range links in systems like airline routes exceeding 100 km.[88] This embedding affects network topology, promoting local connections and limiting long-range ones unless mediated by hubs.[89] A prominent class of spatial networks is planar graphs, which can be drawn on a plane without edge crossings, a property essential for systems like road layouts or power grids. Planar graphs satisfy Euler's formula, N−E+F=2N - E + F = 2, where NN is the number of nodes, EE the edges, and FF the faces, implying an upper bound E≤3N−6E \leq 3N - 6 for simple connected graphs.[88] Spatial constraints in these networks enforce low average degrees, typically around 3 in European road systems or 2 in U.S. ones, with degree distributions that are exponentially decaying rather than power-law.[88] Crossings are minimized to optimize efficiency, as seen in urban street patterns that balance connectivity and space.[90] Key metrics in spatial networks capture geometric influences on structure. Spatial clustering coefficients are elevated due to proximity-based connections, with average values around 0.59 in geometric random graphs and higher in transportation systems compared to non-spatial counterparts.[88] Distance decay manifests as a reduction in connection probability or link strength with increasing separation, often exponentially in short-range systems (e.g., scale ~1000 km in airlines) or via power laws like P(r)∼r−2P(r) \sim r^{-2} for urban trips over 1–100 km.[88] These metrics highlight how space induces assortativity by distance, where nearby nodes form denser subgraphs.[89] Models of spatial networks include lattice structures, which are regular grids enforcing planarity and short path lengths scaling as ⟨ℓ⟩∼N1/2\langle \ell \rangle \sim N^{1/2} in two dimensions.[88] Navigation graphs, such as road networks, exhibit betweenness centrality hotspots at key junctions, enabling efficient routing despite spatial embedding; these often combine small-world properties with scale-free hubs for optimal navigability.[88] In applications like transportation, airline networks use gravity models to weight links, where flow Tij∼PiPj/dijσT_{ij} \sim P_i P_j / d_{ij}^\sigma with σ≈2\sigma \approx 2, predicting higher traffic between populous origins and destinations despite distance deterrence.[88] Wireless sensor networks leverage spatial models for coverage, with short-range links modeled via distance-dependent probabilities to ensure connectivity in ad-hoc deployments.[91] These frameworks underscore spatial networks' role in optimizing real-world systems under geometric constraints.[89]

Recurrence Networks

Recurrence networks represent a method for reconstructing complex networks from univariate time series data, enabling the analysis of underlying dynamical systems by mapping temporal recurrences into graph structures.[92] These networks are constructed by interpreting the recurrence matrix of a time series—derived from phase space reconstruction—as the adjacency matrix of a graph, where nodes correspond to states in the embedded phase space and edges indicate proximity between those states. This approach draws from the theory of recurrence plots, originally introduced for visualizing periodicities and structural patterns in dynamical systems. Unlike traditional network representations, recurrence networks emphasize nonlinear dependencies and topological features that reveal the system's complexity without assuming predefined connectivity. The construction of recurrence networks typically begins with phase space reconstruction using time-delay embedding, where a scalar time series $ x(t) $ is transformed into a higher-dimensional vector $ \mathbf{x}(i) = (x(i), x(i+\tau), \dots, x(i+(m-1)\tau)) $, with embedding dimension $ m $ and delay $ \tau $. Edges are then formed based on a distance threshold $ \epsilon $, connecting states $ \mathbf{x}(i) $ and $ \mathbf{x}(j) $ if $ |\mathbf{x}(i) - \mathbf{x}(j)| < \epsilon $, resulting in an $ \epsilon $-recurrence network.[92] Alternative constructions include visibility graphs, which connect time series points if no intermediate point obstructs the "line of sight," effectively capturing monotonic trends, or k-nearest neighbor networks in phase space, where each state links to its $ k $ closest neighbors to form a sparse graph. These methods allow for the inference of causality in multivariate settings through directed links in inter-system recurrence networks, where asymmetric recurrences between paired time series indicate directional influences. Recurrence quantification analysis (RQA) metrics, such as determinism—which measures the fraction of recurrent points forming diagonal lines in the recurrence plot—provide quantitative insights into network properties like periodicity and chaos.[92] In applications, recurrence networks have been employed to analyze climate data, such as palaeoclimate proxy records, where they detect regime transitions and nonlinear dynamics in long-term environmental time series. In neuroscience, these networks reconstruct brain connectivity from electroencephalogram (EEG) signals, revealing functional interactions and detecting nonlinearity in neural activity patterns during cognitive tasks. For instance, RQA metrics applied to EEG-derived recurrence networks quantify determinism to distinguish healthy brain states from pathological ones, such as in epilepsy. Limitations of recurrence networks include sensitivity to the choice of embedding parameters $ m $ and $ \tau $, which must satisfy conditions outlined in Takens' embedding theorem to faithfully reconstruct the attractor from a single time series. Improper selection can lead to distorted topologies, and while the method excels at detecting nonlinearity, it may not reliably differentiate deterministic chaos from stochastic processes without additional validation.

Processes on Networks

Spread and Diffusion

The spread and diffusion of information, diseases, or other influences through networks is modeled using dynamical processes that capture propagation along edges. These models reveal how network structure governs the extent and speed of dissemination, often leading to phase transitions where small perturbations grow into large-scale outbreaks. Key frameworks include compartmental models like SIR, percolation approaches for connectivity thresholds, and cascade models for probabilistic activation, each highlighting the role of topology in facilitating or hindering diffusion. The Susceptible-Infected-Recovered (SIR) model partitions network nodes into three states: susceptible (S), capable of infection; infected (I), actively spreading the influence; and recovered (R), immune and non-infectious.[93] Transition from S to I occurs at rate β\beta proportional to the number of infected neighbors, while I to R happens at constant rate γ\gamma, independent of contacts.[93] In the mean-field approximation for homogeneous networks, the basic reproduction number R0R_0, representing the expected secondary infections per case in a fully susceptible population, is R0=βγ⟨k⟩R_0 = \frac{\beta}{\gamma} \langle k \rangle, where ⟨k⟩\langle k \rangle is the average degree; epidemics occur when R0>1R_0 > 1.[93] This dynamic yields a sigmoidal growth curve for infections, with the final outbreak size determined by solving self-consistent equations for the probability that a node remains uninfected.[93] Percolation theory analogizes diffusion to the random occupation of network elements, identifying thresholds for the emergence of a giant connected component that enables widespread propagation. In bond percolation, edges are occupied with probability pp, and the process percolates—forming a spanning cluster—above a critical threshold pcp_c, beyond which a macroscopic fraction of nodes connects in the giant component. Site percolation similarly occupies nodes with probability qq, with its threshold qcq_c marking the onset of a giant susceptible cluster; for Erdős-Rényi networks, pc≈1/⟨k⟩p_c \approx 1/\langle k \rangle and qc≈1/(⟨k⟩+1)q_c \approx 1/(\langle k \rangle + 1), but these vary with topology. The emergence of the giant component signals a percolation transition, often continuous, where local connections coalesce into global connectivity, mirroring epidemic invasion or information floods. Diffusion processes like the independent cascade model treat spread as a one-shot probabilistic activation along edges, suitable for viral marketing or rumor propagation.[94] Here, each newly activated node vv attempts to activate each inactive neighbor ww with success probability pv,wp_{v,w} (often uniform pp), but only once; activations proceed in discrete steps until no further spread occurs.[94] This non-Markovian process captures irreversible influences, with the total activated set depending on initial seeds.[94] Influence maximization, selecting kk seeds to optimize expected spread, is NP-hard but approximated greedily by iteratively adding the node maximizing marginal gain, achieving a (1−1/e)(1 - 1/e)-approximation guarantee.[94] Network heterogeneity profoundly affects diffusion thresholds, particularly in scale-free topologies with power-law degree distributions. High-degree hubs lower the effective percolation threshold, enabling outbreaks at transmission rates near zero in the infinite-size limit, as the branching factor ⟨k(k−1)⟩/⟨k⟩\langle k(k-1) \rangle / \langle k \rangle diverges. In such networks, even weak influences can rapidly traverse the system via hubs, contrasting with homogeneous networks requiring R0>1R_0 > 1 for persistence; degree distributions thus modulate vulnerability, with scale-free structures exhibiting vanishing epidemic thresholds.

Immunization Strategies

Immunization strategies in network theory aim to mitigate the spread of epidemics or cascading failures by selectively removing or vaccinating nodes, thereby disrupting percolation paths and raising the epidemic threshold. These approaches are particularly crucial in heterogeneous networks, where random immunization often proves inefficient due to the persistence of highly connected hubs. By targeting structurally important nodes, immunization can achieve global protection with a fraction of the resources required for uniform strategies, as demonstrated in models like the susceptible-infected-recovered (SIR) framework. Targeted immunization focuses on vaccinating nodes with high centrality measures, such as degree or betweenness, to maximize disruption of transmission pathways. In high-degree targeted strategies, the most connected nodes (hubs) are prioritized, as their removal fragments the network more effectively than random selection; for instance, in scale-free networks generated by the Barabási-Albert model, immunizing just 16% of the highest-degree nodes can eradicate epidemics, compared to near-total coverage needed for random immunization.[95] Betweenness-based targeting immunizes nodes that lie on many shortest paths, bridging communities and facilitating spread; this approach outperforms degree-based methods in some empirical networks by requiring 5% to 50% fewer vaccinations to achieve the same protection level, though it demands greater computational resources for centrality computation. Overall, targeted strategies are far more efficient than random immunization in heterogeneous topologies but require complete network knowledge, limiting their practicality in real-time scenarios.[95] Acquaintance immunization offers a practical alternative that approximates targeted effects without global information, by randomly selecting nodes and then vaccinating one of their neighbors. This method leverages the fact that neighbors of random nodes are more likely to be high-degree, achieving near-optimal protection; in scale-free networks with degree exponent γ\gamma between 2 and 3, the critical immunization fraction fcf_c is approximately 0.25, a dramatic improvement over the fc→1f_c \to 1 for random immunization. The strategy's efficiency stems from a modified percolation threshold, where the probability of immunizing a node of degree kk scales with kk, yielding fc≈⟨k⟩⟨k2⟩−⟨k⟩f_c \approx \frac{\langle k \rangle}{\langle k^2 \rangle - \langle k \rangle} in the large-network limit. Ring vaccination, inspired by contact-tracing protocols, immunizes the immediate contacts of identified infected individuals to contain local outbreaks. Modeled as a mixed bond-node percolation process on SIR dynamics, it proves effective when tracing efficiency is high, halting epidemics by vaccinating a ring around cases; optimal allocation minimizes the giant outbreak size, with success depending on the fraction of traced contacts vaccinated, often requiring less than 20% coverage in clustered networks if tracing covers over 80% of edges. This strategy excels in reactive scenarios, complementing preventive measures like targeted immunization. Key metrics for evaluating these strategies include the critical immunization fraction fcf_c, the minimum proportion of nodes that must be immunized to prevent a giant connected component or epidemic outbreak. In Erdős–Rényi random graphs, fc=1−1/λf_c = 1 - 1/\lambda (where λ\lambda is the mean degree times transmission probability), typically around 0.5–0.8 for realistic epidemics, allowing robust protection with moderate effort. In contrast, scale-free networks exhibit fc→1f_c \to 1 under random immunization due to persistent hubs, but targeted and acquaintance methods reduce fcf_c to 0.1–0.3, highlighting the topology-dependent vulnerability and the superiority of structure-aware approaches.[95]
StrategyCritical Fraction fcf_c in Scale-Free NetworksCritical Fraction fcf_c in Random GraphsKey AdvantageCitation
Random≈1\approx 11−1/λ≈0.5–0.81 - 1/\lambda \approx 0.5–0.8Simple implementation
Targeted (Degree)≈0.16\approx 0.16 (for λ=0.25\lambda=0.25)Lower than random, but less studiedMaximizes hub disruption[95]
Acquaintance≈0.25\approx 0.25Comparable to targetedNo global knowledge needed
Ring<0.2 (with high tracing)Effective locally, scales with clustersReactive containment

Optimization Techniques

Optimization techniques in network theory encompass algorithmic methods designed to enhance the efficiency, connectivity, and performance of networks by solving problems such as finding optimal paths, maximizing flows, and minimizing connection costs. These approaches are fundamental in graph-based models where nodes represent entities and edges denote relationships or capacities, allowing for the computation of solutions that minimize total weight or maximize throughput under constraints. Seminal algorithms address specific subproblems, enabling applications in diverse domains by providing provably optimal or near-optimal structures. Shortest path algorithms compute the minimum-weight path between nodes in a weighted graph, crucial for routing and navigation tasks. Dijkstra's algorithm, introduced in 1959, efficiently finds the shortest paths from a single source to all other nodes in graphs with non-negative edge weights by maintaining a priority queue of tentative distances and iteratively selecting the node with the smallest distance for relaxation.[96] For all-pairs shortest paths, the Floyd-Warshall algorithm, developed in 1962, uses dynamic programming to compute the minimum distances between every pair of nodes, handling both positive and negative weights (provided no negative cycles exist) through iterative updates on a distance matrix. An extension, the A* algorithm from 1968, incorporates heuristics to guide the search toward the goal, reducing computational overhead in large search spaces by evaluating nodes based on an estimated total cost function $ f(n) = g(n) + h(n) $, where $ g(n) $ is the path cost from the start and $ h(n) $ is a heuristic estimate to the goal, ensuring optimality if the heuristic is admissible.[97] Maximum flow problems seek to determine the maximum rate at which material or information can be sent from a source to a sink in a capacitated network, with the minimum cut representing the bottleneck. The Ford-Fulkerson algorithm, proposed in 1956, solves this by iteratively finding augmenting paths in the residual graph and augmenting the flow until no such path exists, establishing the max-flow min-cut theorem that equates the maximum flow value to the minimum capacity of a source-sink cut.[98] Capacities are often modeled using the incidence matrix of the graph, where rows correspond to nodes and columns to edges, with entries indicating flow directions and constraints ensuring that the absolute flow on each edge does not exceed its capacity $ c_e \geq |f_e| $.[98] Network design techniques focus on constructing minimal-cost subgraphs that maintain connectivity. Minimum spanning trees (MSTs) connect all nodes with the least total edge weight, avoiding cycles. Kruskal's algorithm, from 1956, achieves this by sorting edges in non-decreasing order and adding them greedily if they do not form cycles, using union-find for efficiency. Prim's algorithm, published in 1957, grows the tree from an arbitrary starting node by repeatedly selecting the minimum-weight edge connecting a tree node to a non-tree node, suitable for dense graphs with priority queue implementations. For scenarios requiring connections among a subset of nodes (terminals) with optional Steiner nodes to reduce cost, the Steiner tree problem extends MSTs; approximation algorithms, such as those achieving a 1.55-approximation ratio, are used due to NP-hardness, as surveyed in foundational works on graphic Steiner trees.[99] These techniques find practical use in routing protocols for communication networks, where shortest path algorithms like Dijkstra underpin protocols such as OSPF to minimize latency in packet forwarding, and in supply chain resilience, where maximum flow models optimize resource distribution across logistics networks to handle disruptions while minimizing costs. MST-based designs further enhance supply chain topologies by identifying efficient backbone structures for distribution hubs.[100]

References

  1. [PDF] Chapter One - Princeton University
  2. An introduction to networks - Math Insight
  3. [PDF] Network Science - CNS
  4. Graph Theory -- from Wolfram MathWorld
  5. Königsberg Bridge Problem -- from Wolfram MathWorld
  6. Tree -- from Wolfram MathWorld
  7. A translation of "Graphok és matrixok" by Dénes Kőnig (1931) - arXiv
  8. Spread of information through a population with socio-structural bias
  9. (PDF) The Development of Social Network Analysis - ResearchGate
  10. [PDF] On random graphs I - SNAP: Stanford
  11. [PDF] ON THE EVOLUTION OF RANDOM GRAPHS - SNAP: Stanford
  12. [PDF] An Experimental Study of the Small World Problem - SNAP: Stanford
  13. [PDF] Emergence of Scaling in Random Networks - SNAP: Stanford
  14. About INSNA - International Network for Social Network Analysis
  15. (PDF) Pajek-program for large Network analysis - ResearchGate
  16. [PDF] GRAPH THEORY WITH APPLICATIONS
  17. [PDF] graph theory: basic definitions and theorems
  18. [PDF] Graph and Network Theory - arXiv
  19. Bridging the gap between graphs and networks - Nature
  20. [PDF] 6.042J Chapter 5: Graph theory - MIT OpenCourseWare
  21. [PDF] 6.207/14.15: Networks Lecture 2: Graph Theory and Social Networks
  22. Graph theory: graph types and edge properties | Network analysis of ...
  23. [PDF] Predicting Attributes of Nodes Using Network Structure - arXiv
  24. [PDF] Label Informed Attributed Network Embedding
  25. Network definition - Math Insight
  26. [PDF] 1 Network basics - Santa Fe Institute
  27. https://users.dimi.uniud.it/~massimo.franceschet/teaching/datascience/network/graphtheory.html
  28. Node degree definition - Math Insight
  29. 6.1 definition of terms and notation - MIT
  30. [PDF] Collective dynamics of 'small-world' networks - SNAP: Stanford
  31. path length - Complexity Explorer
  32. [PDF] Introduction to Network Theory
  33. [PDF] Random Graph Theory - Jackson State University
  34. CSCI 2824 Lecture 29: Graph Theory (Basics)
  35. [PDF] Chapter 8 Graphs: Definition, Applications, Representation
  36. 5.11 Directed Graphs
  37. [PDF] 6.042J Chapter 6: Directed graphs - MIT OpenCourseWare
  38. Analysis of weighted networks - Physical Review Link Manager
  39. [PDF] Graph Theory for Network Science - Jackson State University
  40. Multilayer networks | Journal of Complex Networks - Oxford Academic
  41. Balance in signed networks | Phys. Rev. E
  42. The Adjacency Matrix | An Introduction to Algebraic Graph Theory
  43. Incidence Matrix -- from Wolfram MathWorld
  44. [PDF] Graphs and Matrices - Arizona Math
  45. [PDF] Eigenvalues and the Laplacian of a graph - Fan Chung Graham
  46. [PDF] Algebraic connectivity of graphs. - SNAP: Stanford
  47. The Structure and Function of Complex Networks | SIAM Review
  48. A robust method for fitting degree distributions of complex networks
  49. Efficient sampling algorithm for estimating subgraph concentrations ...
  50. Structure and function of the feed-forward loop network motif - PNAS
  51. Collective dynamics of 'small-world' networks - Nature
  52. Emergence of Scaling in Random Networks - Science
  53. [PDF] A Faster Algorithm for Betweenness Centrality
  54. [PDF] A. Bavelas, 1950, Communication Patterns in Task-Oriented Groups ...
  55. [PDF] Technique for Analyzing Overlapping Memberships
  56. [PDF] The PageRank Citation Ranking: Bringing Order to the Web
  57. [PDF] Centralities in Large Networks: Algorithms and Observations
  58. [PDF] Fast Approximation of Betweenness Centrality through Sampling
  59. Assortative Mixing in Networks | Phys. Rev. Lett.
  60. Mixing patterns in networks | Phys. Rev. E
  61. Finding and evaluating community structure in networks - arXiv
  62. [0803.0476] Fast unfolding of communities in large networks - arXiv
  63. [PDF] Normalized cuts and image segmentation - People @EECS
  64. Resolution limit in community detection | PNAS
  65. Comparing community structure identification - cond-mat - arXiv
  66. Social Network Analysis - Cambridge University Press & Assessment
  67. Best Practices for Modeling Egocentric Social Network Data and ...
  68. The Analysis of Social Networks - PMC - PubMed Central
  69. Structural Holes - Harvard University Press
  70. Markov Graphs on JSTOR
  71. The Strength of Weak Ties | American Journal of Sociology
  72. A large-scale community structure analysis in Facebook
  73. [PDF] The anatomy of a large-scale hypertextual Web search engine '
  74. Co‐citation in the scientific literature: A new measure of the ...
  75. The structure of scientific collaboration networks - PNAS
  76. Graph based anomaly detection and description: a survey
  77. Network biology: understanding the cell's functional organization
  78. What is flux balance analysis? - PMC - NIH
  79. The human connectome: a complex network - Sporns - 2011
  80. Lethality and centrality in protein networks - Nature
  81. Synthetic lethality: General principles, utility and detection using ...
  82. Homeostasis and Differentiation in Random Genetic Control Networks
  83. Food-web structure and network theory: The role of connectance ...
  84. https://doi.org/10.1038/srep00469
  85. [PDF] Spatial networks
  86. [PDF] Spatial networks | HAL-SHS
  87. The simplicity of planar networks | Scientific Reports - Nature
  88. Spatial networks with wireless applications - ScienceDirect.com
  89. Epidemic processes in complex networks | Rev. Mod. Phys.
  90. Maximizing the spread of influence through a social network
  91. [cond-mat/0107066] Immunization of complex networks - arXiv
  92. A note on two problems in connexion with graphs
  93. [PDF] astar.pdf - Stanford AI Lab
  94. [PDF] maximal flow through a network - lr ford, jr. and dr fulkerson
  95. Steiner tree problems - Hwang - 1992 - Wiley Online Library
  96. Network optimization in supply chain management and financial ...
User Avatar
No comments yet.