Search

Politically divided societies are also often divided emotionally: people like and trust those with similar political views (in-group favoritism) while disliking and distrusting those with different views (out-group animosity). This phenomenon, called affective polarization, influences individual decisions, including seemingly apolitical choices such as whether to wear a mask or what car to buy. We present a dynamical model of decision-making in an affectively polarized society, identifying three potential global outcomes separated by a sharp boundary in the parameter space: consensus, partisan polarization, and non-partisan polarization. Analysis reveals that larger out-group animosity compared to in-group favoritism, i.e. more hate than love, is sufficient for polarization, while larger in-group favoritism compared to out-group animosity, i.e., more love than hate, is necessary for consensus. We also show that, counter-intuitively, increasing cross-party connections facilitates polarization, and that by emphasizing partisan differences, mass media creates self-fulfilling prophecies that lead to polarization. Affective polarization also creates tipping points in the opinion landscape where one group suddenly reverses their trends. Our findings aid in understanding and addressing the cascading effects of affective polarization, offering insights for strategies to mitigate polarization.

Quantum algorithms provide an exponential speedup for solving certain classes of linear systems, including those that model geologic fracture flow. However, this revolutionary gain in efficiency does not come without difficulty. Quantum algorithms require that problems satisfy not only algorithm-specific constraints, but also application-specific ones. Otherwise, the quantum advantage carefully attained through algorithmic ingenuity can be entirely negated. Previous work addressing quantum algorithms for geologic fracture flow has illustrated core algorithmic approaches while incrementally removing assumptions. This work addresses two further requirements for solving geologic fracture flow systems with quantum algorithms: efficient system state preparation and efficient information extraction. Our approach to addressing each is consistent with an overall exponential speed-up., Comment: 13 pages, 12 figures, LA-UR-23-31328

Modeling gas flow through fractures of subsurface rock is a particularly challenging problem because of the heterogeneous nature of the material. High-fidelity simulations using discrete fracture network (DFN) models are one methodology for predicting gas particle breakthrough times at the surface, but are computationally demanding. We propose a Bayesian machine learning method that serves as an efficient surrogate model, or emulator, for these three-dimensional DFN simulations. Our model trains on a small quantity of simulation data and, using a graph/path-based decomposition of the fracture network, rapidly predicts quantiles of the breakthrough time distribution. The approach, based on Gaussian Process Regression (GPR), outputs predictions that are within 20-30% of high-fidelity DFN simulation results. Unlike previously proposed methods, it also provides uncertainty quantification, outputting confidence intervals that are essential given the uncertainty inherent in subsurface modeling. Our trained model runs within a fraction of a second, which is considerably faster than other methods with comparable accuracy and multiple orders of magnitude faster than high-fidelity simulations.

Real-world networks are rarely static. Recently, there has been increasing interest in both network growth and network densification, in which the number of edges scales superlinearly with the number of nodes. Less studied but equally important, however, are scaling laws of higher-order cliques, which can drive clustering and network redundancy. In this paper, we study how cliques grow with network size, by analyzing several empirical networks from emails to Wikipedia interactions. Our results show superlinear scaling laws whose exponents increase with clique size, in contrast to predictions from a previous model. We then show that these results are in qualitative agreement with a new model that we propose, the Local Preferential Attachment Model, where an incoming node links not only to a target node but also to its higher-degree neighbors. Our results provide new insights into how networks grow and where network redundancy occurs., Comment: 14 pages, 11 figures. Paper is in press at Physical Review E

Research collaborations provide the foundation for scientific advances, but we have only recently begun to understand how they form and grow on a global scale. Here we analyze a model of the growth of research collaboration networks to explain the empirical observations that the number of collaborations scales superlinearly with institution size, though at different rates (heterogeneous densification), the number of institutions grows as a power of the number of researchers (Heaps' law) and institution sizes approximate Zipf's law. This model has three mechanisms: (i) researchers are preferentially hired by large institutions, (ii) new institutions trigger more potential institutions, and (iii) researchers collaborate with friends-of-friends. We show agreement between these assumptions and empirical data, through analysis of co-authorship networks spanning two centuries. We then develop a theoretical understanding of this model, which reveals emergent heterogeneous scaling such that the number of collaborations between institutions scale with an institution's size., Comment: arXiv admin note: text overlap with arXiv:2001.08734

Research institutions provide the infrastructure for scientific discovery, yet their role in the production of knowledge is not well characterized. To address this gap, we analyze interactions of researchers within and between institutions from millions of scientific papers. Our analysis reveals that the number of collaborations scales superlinearly with institution size, though at different rates (heterogeneous densification). We also find that the number of institutions scales with the number of researchers as a power law (Heaps' law) and institution sizes approximate Zipf's law. These patterns can be reproduced by a simple model with three mechanisms: (i) researchers collaborate with friends-of-friends, (ii) new institutions trigger more potential institutions, and (iii) researchers are preferentially hired by large institutions. This model reveals an economy of scale in research: larger institutions grow faster and amplify collaborations. Our work provides a new understanding of emergent behavior in research institutions and how they facilitate innovation., Comment: 31 pages double-spaced (12 pages main text) and 23 figures (3 figures main text)

Network topologies can be non-trivial, due to the complex underlying behaviors that form them. While past research has shown that some processes on networks may be characterized by low-order statistics describing nodes and their neighbors, such as degree assortativity, these quantities fail to capture important sources of variation in network structure. We introduce a property called transsortativity that describes correlations among a node's neighbors, generalizing these statistics from immediate one-hop neighbors to two-hop neighbors. We describe how transsortativity can be systematically varied, independently of the network's degree distribution and assortativity. Moreover, we show that it can significantly impact the spread of contagions as well as the perceptions of neighbors, known as the majority illusion. Our work improves our ability to create and analyze more realistic models of complex networks., Comment: 6 pages, 5 figures

We propose a machine learning approach to address a key challenge in materials science: predicting how fractures propagate in brittle materials under stress, and how these materials ultimately fail. Our methods use deep learning and train on simulation data from high-fidelity models, emulating the results of these models while avoiding the overwhelming computational demands associated with running a statistically significant sample of simulations. We employ a graph convolutional network that recognizes features of the fracturing material and a recurrent neural network that models the evolution of these features, along with a novel form of data augmentation that compensates for the modest size of our training data. We simultaneously generate predictions for qualitatively distinct material properties. Results on fracture damage and length are within 3% of their simulated values, and results on time to material failure, which is notoriously difficult to predict even with high-fidelity models, are within approximately 15% of simulated values. Once trained, our neural networks generate predictions within seconds, rather than the hours needed to run a single simulation.

Networks facilitate the spread of cascades, allowing a local perturbation to percolate via interactions between nodes and their neighbors. We investigate how network structure affects the dynamics of a spreading cascade. By accounting for the joint degree distribution of a network within a generating function framework, we can quantify how degree correlations affect both the onset of global cascades and the propensity of nodes of specific degree class to trigger large cascades. However, not all degree correlations are equally important in a spreading process. We introduce a new measure of degree assortativity that accounts for correlations among nodes relevant to a spreading cascade. We show that the critical point defining the onset of global cascades has a monotone relationship to this new assortativity measure. In addition, we show that the choice of nodes to seed the largest cascades is strongly affected by degree correlations. Contrary to traditional wisdom, when degree assortativity is positive, low degree nodes are more likely to generate largest cascades. Our work suggests that it may be possible to tailor spreading processes by manipulating the higher-order structure of networks., Comment: 9 pages, 8 figures

Vehicle recognition and classification have broad applications, ranging from traffic flow management to military target identification. We demonstrate an unsupervised method for automated identification of moving vehicles from roadside audio sensors. Using a short-time Fourier transform to decompose audio signals, we treat the frequency signature in each time window as an individual data point. We then use a spectral embedding for dimensionality reduction. Based on the leading eigenvectors, we relate the performance of an incremental reseeding algorithm to that of spectral clustering. We find that incremental reseeding accurately identifies individual vehicles using their acoustic signatures.

We propose a method for recognizing moving vehicles, using data from roadside audio sensors. This problem has applications ranging widely, from traffic analysis to surveillance. We extract a frequency signature from the audio signal using a short-time Fourier transform, and treat each time window as an individual data point to be classified. By applying a spectral embedding, we decrease the dimensionality of the data sufficiently for K-nearest neighbors to provide accurate vehicle identification., Comment: Proceedings of the 15th IEEE International Conference on Networking, Sensing and Control (2018)

Structural and topological information play a key role in modeling flow and transport through fractured rock in the subsurface. Discrete fracture network (DFN) computational suites such as dfnWorks are designed to simulate flow and transport in such porous media. Flow and transport calculations reveal that a small backbone of fractures exists, where most flow and transport occurs. Restricting the flowing fracture network to this backbone provides a significant reduction in the network's effective size. However, the particle tracking simulations needed to determine the reduction are computationally intensive. Such methods may be impractical for large systems or for robust uncertainty quantification of fracture networks, where thousands of forward simulations are needed to bound system behavior. In this paper, we develop an alternative network reduction approach to characterizing transport in DFNs, by combining graph theoretical and machine learning methods. We consider a graph representation where nodes signify fractures and edges denote their intersections. Using random forest and support vector machines, we rapidly identify a subnetwork that captures the flow patterns of the full DFN, based primarily on node centrality features in the graph. Our supervised learning techniques train on particle-tracking backbone paths found by dfnWorks, but run in negligible time compared to those simulations. We find that our predictions can reduce the network to approximately 20% of its original size, while still generating breakthrough curves consistent with those of the original network., Comment: Computational Geosciences (2018)

In numerous physical models on networks, dynamics are based on interactions that exclusively involve properties of a node's nearest neighbors. However, a node's local view of its neighbors may systematically bias perceptions of network connectivity or the prevalence of certain traits. We investigate the strong friendship paradox, which occurs when the majority of a node's neighbors have more neighbors than does the node itself. We develop a model to predict the magnitude of the paradox, showing that it is enhanced by negative correlations between degrees of neighboring nodes. We then show that by including neighbor-neighbor correlations, which are degree correlations one step beyond those of neighboring nodes, we accurately predict the impact of the strong friendship paradox in real-world networks. Understanding how the paradox biases local observations can inform better measurements of network structure and our understanding of collective phenomena.

Real-world networks are often organized as modules or communities of similar nodes that serve as functional units. These networks are also rich in content, with nodes having distinguishing features or attributes. In order to discover a network's modular structure, it is necessary to take into account not only its links but also node attributes. We describe an information-theoretic method that identifies modules by compressing descriptions of information flow on a network. Our formulation introduces node content into the description of information flow, which we then minimize to discover groups of nodes with similar attributes that also tend to trap the flow of information. The method has several advantages: it is conceptually simple and does not require ad-hoc parameters to specify the number of modules or to control the relative contribution of links and node attributes to network structure. We apply the proposed method to partition real-world networks with known community structure. We demonstrate that adding node attributes helps recover the underlying community structure in content-rich networks more effectively than using links alone. In addition, we show that our method is faster and more accurate than alternative state-of-the-art algorithms., Comment: 10 pages

We propose a method to improve image clustering using sparse text and the wisdom of the crowds. In particular, we present a method to fuse two different kinds of document features, image and text features, and use a common dictionary or "wisdom of the crowds" as the connection between the two different kinds of documents. With the proposed fusion matrix, we use topic modeling via non-negative matrix factorization to cluster documents.

We present a graph-based variational algorithm for classification of high-dimensional data, generalizing the binary diffuse interface model to the case of multiple classes. Motivated by total variation techniques, the method involves minimizing an energy functional made up of three terms. The first two terms promote a stepwise continuous classification function with sharp transitions between classes, while preserving symmetry among the class labels. The third term is a data fidelity term, allowing us to incorporate prior information into the model in a semi-supervised framework. The performance of the algorithm on synthetic data, as well as on the COIL and MNIST benchmark datasets, is competitive with state-of-the-art graph-based multiclass segmentation methods., Comment: 16 pages, to appear in Springer's Lecture Notes in Computer Science volume "Pattern Recognition Applications and Methods 2013", part of series on Advances in Intelligent and Soft Computing

Spectral clustering is widely used to partition graphs into distinct modules or communities. Existing methods for spectral clustering use the eigenvalues and eigenvectors of the graph Laplacian, an operator that is closely associated with random walks on graphs. We propose a new spectral partitioning method that exploits the properties of epidemic diffusion. An epidemic is a dynamic process that, unlike the random walk, simultaneously transitions to all the neighbors of a given node. We show that the replicator, an operator describing epidemic diffusion, is equivalent to the symmetric normalized Laplacian of a reweighted graph with edges reweighted by the eigenvector centralities of their incident nodes. Thus, more weight is given to edges connecting more central nodes. We describe a method that partitions the nodes based on the componentwise ratio of the replicator's second eigenvector to the first, and compare its performance to traditional spectral clustering techniques on synthetic graphs with known community structure. We demonstrate that the replicator gives preference to dense, clique-like structures, enabling it to more effectively discover communities that may be obscured by dense intercommunity linking., Comment: 6 pages, to appear in Physical Review E

We analyze the component evolution in inhomogeneous random intersection graphs when the average degree is close to 1. As the average degree increases, the size of the largest component in the random intersection graph goes through a phase transition. We give bounds on the size of the largest components before and after this transition. We also prove that the largest component after the transition is unique. These results are similar to the phase transition in Erd\H{o}s-R\'enyi random graphs; one notable difference is that the jump in the size of the largest component varies in size depending on the parameters of the random intersection graph., Comment: 18 pages

We present a graph-based variational algorithm for multiclass classification of high-dimensional data, motivated by total variation techniques. The energy functional is based on a diffuse interface model with a periodic potential. We augment the model by introducing an alternative measure of smoothness that preserves symmetry among the class labels. Through this modification of the standard Laplacian, we construct an efficient multiclass method that allows for sharp transitions between classes. The experimental results demonstrate that our approach is competitive with the state of the art among other graph-based algorithms., Comment: 9 pages, to appear in Proceedings of the 2nd International Conference on Pattern Recognition Applications and Methods (ICPRAM 2013)

Random intersection graphs (RIGs) are an important random structure with applications in social networks, epidemic networks, blog readership, and wireless sensor networks. RIGs can be interpreted as a model for large randomly formed non-metric data sets. We analyze the component evolution in general RIGs, and give conditions on existence and uniqueness of the giant component. Our techniques generalize existing methods for analysis of component evolution: we analyze survival and extinction properties of a dependent, inhomogeneous Galton-Watson branching process on general RIGs. Our analysis relies on bounding the branching processes and inherits the fundamental concepts of the study of component evolution in Erd\H{o}s-R\'enyi graphs. The major challenge comes from the underlying structure of RIGs, which involves its both the set of nodes and the set of attributes, as well as the set of different probabilities among the nodes and attributes.

The mincut graph bisection problem involves partitioning the n vertices of a graph into disjoint subsets, each containing exactly n/2 vertices, while minimizing the number of "cut" edges with an endpoint in each subset. When considered over sparse random graphs, the phase structure of the graph bisection problem displays certain familiar properties, but also some surprises. It is known that when the mean degree is below the critical value of 2 log 2, the cutsize is zero with high probability. We study how the minimum cutsize increases with mean degree above this critical threshold, finding a new analytical upper bound that improves considerably upon previous bounds. Combined with recent results on expander graphs, our bound suggests the unusual scenario that random graph bisection is replica symmetric up to and beyond the critical threshold, with a replica symmetry breaking transition possibly taking place above the threshold. An intriguing algorithmic consequence is that although the problem is NP-hard, we can find near-optimal cutsizes (whose ratio to the optimal value approaches 1 asymptotically) in polynomial time for typical instances near the phase transition., Comment: substantially revised section 2, changed figures 3, 4 and 6, made minor stylistic changes and added references

We study the connection between the order of phase transitions in combinatorial problems and the complexity of decision algorithms for such problems. We rigorously show that, for a class of random constraint satisfaction problems, a limited connection between the two phenomena indeed exists. Specifically, we extend the definition of the spine order parameter of Bollobas et al. to random constraint satisfaction problems, rigorously showing that for such problems a discontinuity of the spine is associated with a $2^{\Omega(n)}$ resolution complexity (and thus a $2^{\Omega(n)}$ complexity of DPLL algorithms) on random instances. The two phenomena have a common underlying cause: the emergence of ``large'' (linear size) minimally unsatisfiable subformulas of a random formula at the satisfiability phase transition. We present several further results that add weight to the intuition that random constraint satisfaction problems with a sharp threshold and a continuous spine are ``qualitatively similar to random 2-SAT''. Finally, we argue that it is the spine rather than the backbone parameter whose continuity has implications for the decision complexity of combinatorial problems, and we provide experimental evidence that the two parameters can behave in a different manner., Comment: A revised version of this paper will appear in Annals of Mathematics and Artificial Intelligence

We investigate the phase transition of the 3-coloring problem on random graphs, using the extremal optimization heuristic. 3-coloring is among the hardest combinatorial optimization problems and is closely related to a 3-state anti-ferromagnetic Potts model. Like many other such optimization problems, it has been shown to exhibit a phase transition in its ground state behavior under variation of a system parameter: the graph's mean vertex degree. This phase transition is often associated with the instances of highest complexity. We use extremal optimization to measure the ground state cost and the ``backbone'', an order parameter related to ground state overlap, averaged over a large number of instances near the transition for random graphs of size $n$ up to 512. For graphs up to this size, benchmarks show that extremal optimization reaches ground states and explores a sufficient number of them to give the correct backbone value after about $O(n^{3.5})$ update steps. Finite size scaling gives a critical mean degree value $\alpha_{\rm c}=4.703(28)$. Furthermore, the exploration of the degenerate ground states indicates that the backbone order parameter, measuring the constrainedness of the problem, exhibits a first-order phase transition., Comment: RevTex4, 8 pages, 4 postscript figures, related information available at http://www.physics.emory.edu/faculty/boettcher/

We consider combinatorial optimization problems defined over random ensembles, and study how solution cost increases when the optimal solution undergoes a small perturbation delta. For the minimum spanning tree, the increase in cost scales as delta^2; for the mean-field and Euclidean minimum matching and traveling salesman problems in dimension d>=2, the increase scales as delta^3; this is observed in Monte Carlo simulations in d=2,3,4 and in theoretical analysis of a mean-field model. We speculate that the scaling exponent could serve to classify combinatorial optimization problems into a small number of distinct categories, similar to universality classes in statistical physics., Comment: 5 pages; 3 figures

A recently introduced general-purpose heuristic for finding high-quality solutions for many hard optimization problems is reviewed. The method is inspired by recent progress in understanding far-from-equilibrium phenomena in terms of {\em self-organized criticality,} a concept introduced to describe emergent complexity in physical systems. This method, called {\em extremal optimization,} successively replaces the value of extremely undesirable variables in a sub-optimal solution with new, random ones. Large, avalanche-like fluctuations in the cost function self-organize from this dynamics, effectively scaling barriers to explore local optima in distant neighborhoods of the configuration space while eliminating the need to tune parameters. Drawing upon models used to simulate the dynamics of granular media, evolution, or geology, extremal optimization complements approximation methods inspired by equilibrium statistical physics, such as {\em simulated annealing}. It may be but one example of applying new insights into {\em non-equilibrium phenomena} systematically to hard optimization problems. This method is widely applicable and so far has proved competitive with -- and even superior to -- more elaborate general-purpose heuristics on testbeds of constrained optimization problems with up to $10^5$ variables, such as bipartitioning, coloring, and satisfiability. Analysis of a suitable model predicts the only free parameter of the method in accordance with all experimental results., Comment: Latex, 17 pages, to appear in the {\it Proceedings of the 8th INFORMS Computing Society Conference,} (2003)

We describe a general-purpose method for finding high-quality solutions to hard optimization problems, inspired by self-organized critical models of co-evolution such as the Bak-Sneppen model. The method, called Extremal Optimization, successively eliminates extremely undesirable components of sub-optimal solutions, rather than ``breeding'' better components. In contrast to Genetic Algorithms which operate on an entire ``gene-pool'' of possible solutions, Extremal Optimization improves on a single candidate solution by treating each of its components as species co-evolving according to Darwinian principles. Unlike Simulated Annealing, its non-equilibrium approach effects an algorithm requiring few parameters to tune. With only one adjustable parameter, its performance proves competitive with, and often superior to, more elaborate stochastic optimization procedures. We demonstrate it here on two classic hard optimization problems: graph partitioning and the traveling salesman problem., Comment: 8 pages, Latex, 5 ps-figures included. To appear in ``GECCO-99: Proceedings of the Genetic and Evolutionary Computation Conference,'' (Morgan Kaufmann, San Francisco, 1999)