rvenkat + networks   311

[1711.09504] A Typology of Social Capital and Associated Network Measures
I provide a typology of social capital, breaking it down into seven more fundamental forms of capital: information capital, brokerage capital, coordination and leadership capital, bridging capital, favor capital, reputation capital, and community capital. I discuss how most of these forms of social capital can be identified using different network-based measures.
matthew.jackson  social_networks  networks  teaching 
21 days ago by rvenkat
A criterion for unanimity in French’s theory of social power
French's use of digraph theory in social psychology (see –W31:–n 4473) is extended by providing a necessary and sufficient condition for the attainment of ultimate unanimity of opinions in a power structure. The isomorphism is demonstrated between French's formalization and the theory of higher transition probabilities in Markov chains. The concepts of "automorphic groups" and "power subgroups" are defined and developed
social_influence  social_networks  social_psychology  networks 
29 days ago by rvenkat
A formal theory of social power
This theory illustrates a way by which many complex phenomena about groups can be deduced from a few simple postulates about interpersonal relations. By the application of digraph theory we are able to treat in detail the patterns of relations whose importance has long been noted by the field theorists." Three major postulates are presented as well as a variety of theorems dealing with the effects of the power structure of the group, the effects of communication patterns, the effects of patterns of opinion, and leadership.
social_influence  social_networks  social_psychology  networks 
29 days ago by rvenkat
The ecology of the microbiome: Networks, competition, and stability | Science
The human gut harbors a large and complex community of beneficial microbes that remain stable over long periods. This stability is considered critical for good health but is poorly understood. Here we develop a body of ecological theory to help us understand microbiome stability. Although cooperating networks of microbes can be efficient, we find that they are often unstable. Counterintuitively, this finding indicates that hosts can benefit from microbial competition when this competition dampens cooperative networks and increases stability. More generally, stability is promoted by limiting positive feedbacks and weakening ecological interactions. We have analyzed host mechanisms for maintaining stability—including immune suppression, spatial structuring, and feeding of community members—and support our key predictions with recent data
microbiome  networks  ecology  evolution_of_cooperation  game_theory  for_friends 
5 weeks ago by rvenkat
Structure and dynamical behavior of non-normal networks | Science Advances
We analyze a collection of empirical networks in a wide spectrum of disciplines and show that strong non-normality is ubiquitous in network science. Dynamical processes evolving on non-normal networks exhibit a peculiar behavior, as initial small disturbances may undergo a transient phase and be strongly amplified in linearly stable systems. In addition, eigenvalues may become extremely sensible to noise and have a diminished physical meaning. We identify structural properties of networks that are associated with non-normality and propose simple models to generate networks with a tunable level of non-normality. We also show the potential use of a variety of metrics capturing different aspects of non-normality and propose their potential use in the context of the stability of complex ecosystems.

Also here
https://arxiv.org/abs/1801.07351
networks  linear_algebra  dynamical_system  network_data_analysis  teaching  ? 
5 weeks ago by rvenkat
Interpreting economic complexity | Science Advances
Two network measures known as the economic complexity index (ECI) and product complexity index (PCI) have provided important insights into patterns of economic development. We show that the ECI and PCI are equivalent to a spectral clustering algorithm that partitions a similarity graph into two parts. The measures are also closely related to various dimensionality reduction methods, such as diffusion maps and correspondence analysis. Our results shed new light on the ECI’s empirical success in explaining cross-country differences in gross domestic product per capita and economic growth, which is often linked to the diversity of country export baskets. In fact, countries with high (low) ECI tend to specialize in high-PCI (low-PCI) products. We also find that the ECI and PCI uncover specialization patterns across U.S. states and U.K. regions.
networks  economic_geography  teaching 
5 weeks ago by rvenkat
[1811.10416] Spectra of Sparse Non-Hermitian Random Matrices
Sparse non-Hermitian random matrices arise in the study of disordered physical systems with asymmetric local interactions, and have applications ranging from neural networks to ecosystem dynamics. The spectral characteristics of these matrices provide crucial information on system stability and susceptibility, however, their study is greatly complicated by the twin challenges of a lack of symmetry and a sparse interaction structure. In this review we provide a concise and systematic introduction to the main tools and results in this field. We show how the spectra of sparse non-Hermitian matrices that have a locally tree-like topology can be computed via an analogy with infinite dimensional operators obeying certain recursion relations. With reference to three illustrative examples --- adjacency matrices of regular oriented graphs, adjacency matrices of oriented Erdős-Rényi graphs, and adjacency matrices of weighted oriented Erdős-Rényi graphs --- we demonstrate the use of these methods to obtain both analytic and numerical results for the spectrum, the spectral distribution, the location of outlier eigenvalues, and the statistical properties of eigenvectors.

and related work https://arxiv.org/abs/1206.1512
graph_theory  networks  random_matrix 
5 weeks ago by rvenkat
Misinformation and Conspiracy Theories about Politics and Public Policy
Why do people hold false or unsupported beliefs about politics and public policy and why are so those beliefs so hard to change? This three-credit graduate course will explore the psychological factors that make people vulnerable to misinformation and conspiracy theories and the reasons that corrections so often fail to change their minds. We will also analyze how those tendencies are exploited by political elites and consider possible approaches that journalists, civic reformers, and government officials could employ to combat misperceptions. Students will develop substantive expertise in how to measure, diagnose, and respond to false beliefs about politics and public policy; methodological expertise in reading and analyzing quantitative and experimental research in social science; and analytical writing skills in preparing a final research paper applying one or more theories from the course to help explain the development and spread of a specific misperception or conspiracy theory.
brendan.nyhan  course  misinformation  disinformation  public_opinion  public_policy  conspiracy_theories  political_science  teaching  dmce  networks 
5 weeks ago by rvenkat
Modeling Asymmetric Relationships from Symmetric Networks | Political Analysis | Cambridge Core
Many bilateral relationships requiring mutual agreement produce observable networks that are symmetric (undirected). However, the unobserved, asymmetric (directed) network is frequently the object of scientific interest. We propose a method that probabilistically reconstructs the latent, asymmetric network from the observed, symmetric graph in a regression-based framework. We apply this model to the bilateral investment treaty network. Our approach successfully recovers the true data generating process in simulation studies, extracts new, politically relevant information about the network structure inaccessible to alternative approaches, and has superior predictive performance.

-- latent preference structure is used to infer directionality of edges. But is causal reasoning involved in inferring directionality?
networks  network_data_analysis  international_affairs  causal_inference  ? 
9 weeks ago by rvenkat
Phys. Rev. Lett. 121, 228301 (2018) - Simplicial Activity Driven Model
Many complex systems find a convenient representation in terms of networks: structures made by pairwise interactions (links) of elements (nodes). For many biological and social systems, elementary interactions involve, however, more than two elements, and simplicial complexes are more adequate to describe such phenomena. Moreover, these interactions often change over time. Here, we propose a framework to model such an evolution: the simplicial activity driven model, in which the building block is a simplex of nodes representing a multiagent interaction. We show analytically and numerically that the use of simplicial structures leads to crucial structural differences with respect to the activity driven model, a paradigmatic temporal network model involving only binary interactions. It also impacts the outcome of paradigmatic processes modeling disease propagation or social contagion. In particular, fluctuations in the number of nodes involved in the interactions can affect the outcome of models of simple contagion processes, contrarily to what happens in the activity driven model.
hypergraph  networks  dynamical_system  for_friends 
9 weeks ago by rvenkat
[1709.06005v2] TikZ-network manual
TikZ-network is an open source software project for visualizing graphs and networks in LaTeX. It aims to provide a simple and easy tool to create, visualize and modify complex networks. The packaged is based on the PGF/TikZ languages for producing vector graphics from a geometric/algebraic description. Particular focus is made on the software usability and interoperability with other tools. Simple networks can be directly created within LaTeX, while more complex networks can be imported from external sources (e.g. igraph, networkx, QGIS, ...). Additionally, tikz-network supports visualization of multilayer networks in two and three dimensions. The software is available at: this https URL.
latex  packages  networks 
9 weeks ago by rvenkat
[1811.05008] Choosing to grow a graph: Modeling network formation as discrete choice
We provide a framework for modeling social network formation through conditional multinomial logit models from discrete choice and random utility theory, in which each new edge is viewed as a "choice" made by a node to connect to another node, based on (generic) features of the other nodes available to make a connection. This perspective on network formation unifies existing models such as preferential attachment, triadic closure, and node fitness, which are all special cases, and thereby provides a flexible means for conceptualizing, estimating, and comparing models. The lens of discrete choice theory also provides several new tools for analyzing social network formation; for example, mixtures of existing models can be estimated by adapting known expectation-maximization algorithms, and the significance of node features can be evaluated in a statistically rigorous manner. We demonstrate the flexibility of our framework through examples that analyze a number of synthetic and real-world datasets. For example, we provide rigorous methods for estimating preferential attachment models and show how to separate the effects of preferential attachment and triadic closure. Non-parametric estimates of the importance of degree show a highly linear trend, and we expose the importance of looking carefully at nodes with degree zero. Examining the formation of a large citation graph, we find evidence for an increased role of degree when accounting for age.

--seems related to some of M.O. Jackson's constructions...
networks  dynamics  optimization  game_theory  via:clauset 
november 2018 by rvenkat
[1811.02071] Scale-free Networks Well Done
We bring rigor to the vibrant activity of detecting power laws in empirical degree distributions in real-world networks. We first provide a rigorous definition of power-law distributions, equivalent to the definition of regularly varying distributions in statistics. This definition allows the distribution to deviate from a pure power law arbitrarily but without affecting the power-law tail exponent. We then identify three estimators of these exponents that are proven to be statistically consistent -- that is, converging to the true exponent value for any regularly varying distribution -- and that satisfy some additional niceness requirements. Finally, we apply these estimators to a representative collection of synthetic and real-world data. According to their estimates, real-world scale-free networks are definitely not as rare as one would conclude based on the popular but unrealistic assumption that real-world data comes from power laws of pristine purity, void of noise and deviations.

-- academic snark at its best; this is going to fun
networks  statistics  debates 
november 2018 by rvenkat
Norms in the Wild - Paperback - Cristina Bicchieri - Oxford University Press
The philosopher Cristina Bicchieri here develops her theory of social norms, most recently explained in her 2006 volume The Grammar of Society. Bicchieri challenges many of the fundamental assumptions of the social sciences. She argues that when it comes to human behavior, social scientists place too much stress on rational deliberation. In fact, many choices occur without much deliberation at all. Bicchieri's theory accounts for these automatic components of behavior, where individuals react automatically to cues--those cues often pointing to the social norms that govern our choices in a social world

Bicchieri's work has broad implications not only for understanding human behavior, but for changing it for better outcomes. People have a strong conditional preference for following social norms, but that also means manipulating those norms (and the underlying social expectations) can produce beneficial behavioral changes. Bicchieri's recent work with UNICEF has explored the applicability of her views to issues of human rights and well-being. Is it possible to change social expectations around forced marriage, genital mutilations, and public health practices like vaccinations and sanitation? If so, how? What tools might we use? This short book explores how social norms work, and how changing them--changing preferences, beliefs, and especially social expectations--can potentially improve lives all around the world.

--To-do: compare with Ullmann-Margalit's work. Don't remember the exact connections...
book  norms  dynamics  social_behavior  homophily  contagion  social_influence  networks  social_networks  teaching 
november 2018 by rvenkat
[1810.03579] Long ties accelerate noisy threshold-based contagions
"Changes to network structure can substantially affect when and how widely new ideas, products, and conventions are adopted. In models of biological contagion, interventions that randomly rewire edges (making them "longer") accelerate spread. However, there are other models relevant to social contagion, such as those motivated by myopic best-response in games with strategic complements, in which individual's behavior is described by a threshold number of adopting neighbors above which adoption occurs (i.e., complex contagions). Recent work has argued that highly clustered, rather than random, networks facilitate spread of these complex contagions. Here we show that minor modifications of prior analyses, which make them more realistic, reverse this result. The modification is that we allow very rarely below threshold adoption, i.e., very rarely adoption occurs, where there is only one adopting neighbor. To model the trade-off between long and short edges we consider networks that are the union of cycle-power-k graphs and random graphs on n nodes. We study how the time to global spread changes as we replace the cycle edges with (random) long ties. Allowing adoptions below threshold to occur with order 1/n‾√ probability is enough to ensure that random rewiring accelerates spread. Simulations illustrate the robustness of these results to other commonly-posited models for noisy best-response behavior. We then examine empirical social networks, where we find that hypothetical interventions that (a) randomly rewire existing edges or (b) add random edges reduce time to spread compared with the original network or addition of "short", triad-closing edges, respectively. This substantially revises conclusions about how interventions change the spread of behavior, suggesting that those wanting to increase spread should induce formation of long ties, rather than triad-closing ties."
via:cshalizi  networks  contagion  teaching  for_friends 
october 2018 by rvenkat
[1810.01605] $mathbf{h_alpha}$: An index to quantify an individual's scientific leadership
The α person is the dominant person in a group. We define the α-author of a paper as the author of the paper with the highest h-index among all the coauthors, and an α-paper of a scientist as a paper authored or coauthored by the scientist where he/she is the α-author. For most but not all papers in the literature there is only one α-author. We define the hα index of a scientist as the number of papers in the h-core of the scientist (i.e. the set of papers that contribute to the h-index of the scientist) where this scientist is the α-author. We also define the h′α index of a scientist as the number of α-papers of this scientist that have ≥ h′α citations. hα and h′α contain similar information, while h′α is conceptually more appealing it is harder to obtain from existing databases, hence of less current practical interest. We propose that the hα and/or h′α indices, or other variants discussed in the paper, are useful complements to the h-index of a scientist to quantify his/her scientific achievement, that rectify an inherent drawback of the h-index, its inability to distinguish between authors with different coauthorships patterns. A high h index in conjunction with a high hα/h ratio is a hallmark of scientific leadership.
sociology_of_science  bibliometry  networks 
october 2018 by rvenkat
[1809.08937] Networks and the Resilience and Fall of Empires: a Macro-Comparison of the Imperium Romanum and Imperial China
This paper proposes to proceed from a rather metaphorical application of network terminology on polities and imperial formations of the past to an actual use of tools and concepts of network science. For this purpose, a well established network model of the route system in the Roman Empire and a newly created network model of the infrastructural web of Imperial China are visualised and analysed with regard to their structural properties. Findings indicate that these systems could be understood as large scale complex networks with pronounced differences in centrality and connectivity among places and a hierarchical sequence of clusters across spatial scales from the overregional to the local level. Such properties in turn would influence the cohesion and robustness of imperial networks, as is demonstrated with two tests on vulnerability to node failure and to the collapse of longdistance connectivity. Tentatively, results can be connected with actual historical dynamics and thus hint at underlying network mechanisms of large scale integration and disintegration of political formations.
networks  history  spatial_statistics  network_data_analysis  geography  for_friends  teaching  via:noahpinion 
september 2018 by rvenkat
Diversifying the picture of explanations in biological sciences: ways of combining topology with mechanisms | SpringerLink
Besides mechanistic explanations of phenomena, which have been seriously investigated in the last decade, biology and ecology also include explanations that pinpoint specific mathematical properties as explanatory of the explanandum under focus. Among these structural explanations, one finds topological explanations, and recent science pervasively relies on them. This reliance is especially due to the necessity to model large sets of data with no practical possibility to track the proper activities of all the numerous entities. The paper first defines topological explanations and then explains why topological explanations and mechanisms are different in principle. Then it shows that they are pervasive both in the study of networks—whose importance has been increasingly acknowledged at each level of the biological hierarchy—and in contexts where the notion of selective neutrality is crucial; this allows me to capture the difference between mechanisms and topological explanations in terms of practical modelling practices. The rest of the paper investigates how in practice mechanisms and topologies are combined. They may be articulated in theoretical structures and explanatory strategies, first through a relation of constraint, second in interlevel theories (Sect. 3), or they may condition each other (Sect. 4). Finally, I explore how a particular model can integrate mechanistic informations, by focusing on the recent practice of merging networks in ecology and its consequences upon multiscale modelling (Sect. 5).
philosophy_of_biology  explanation  networks 
september 2018 by rvenkat
Explicating Top-Down Causation Using Networks and Dynamics | Philosophy of Science: Vol 84, No 2
In many fields in the life sciences investigators refer to downward or top-down causal effects. Craver and I defended the view that such cases should be understood in terms of a constitution relation between levels in a mechanism and intralevel causal relations (occurring at any level). We did not, however, specify when entities constitute a higher-level mechanism. In this article I appeal to graph-theoretic representations of networks, now widely employed in systems biology and neuroscience, and associate mechanisms with modules that exhibit high clustering. As a result of interconnections within clusters, mechanisms often exhibit complex dynamic behaviors that constrain how individual components respond to external inputs, a central feature of top-down causation.
philosophy_of_science  networks  social_networks  dynamics  explanation  causality 
september 2018 by rvenkat
[1705.02801] Graph Embedding Techniques, Applications, and Performance: A Survey
Graphs, such as social networks, word co-occurrence networks, and communication networks, occur naturally in various real-world applications. Analyzing them yields insight into the structure of society, language, and different patterns of communication. Many approaches have been proposed to perform the analysis. Recently, methods which use the representation of graph nodes in vector space have gained traction from the research community. In this survey, we provide a comprehensive and structured analysis of various graph embedding techniques proposed in the literature. We first introduce the embedding task and its challenges such as scalability, choice of dimensionality, and features to be preserved, and their possible solutions. We then present three categories of approaches based on factorization methods, random walks, and deep learning, with examples of representative algorithms in each category and analysis of their performance on various tasks. We evaluate these state-of-the-art methods on a few common datasets and compare their performance against one another. Our analysis concludes by suggesting some potential applications and future directions. We finally present the open-source Python library we developed, named GEM (Graph Embedding Methods, available at this https URL), which provides all presented algorithms within a unified interface to foster and facilitate research on the topic.

--Ok as a survey. Works from the following definition of graph embedding.

(Graph embedding) Given a graph G=(V,E),a graph embedding is a mapping f:vi→yi∈Rd∀∈[n]such that d |V |and the function f preserves some proximity measure defined on graph G
graph_theory  survey  geometry  topological_data_analysis  networks  ? 
august 2018 by rvenkat
[1305.2167] The nonlinear heat equation on W-random graphs
For systems of coupled differential equations on a sequence of W-random graphs, we derive the continuum limit in the form of an evolution integral equation. We prove that solutions of the initial value problems (IVPs) for the discrete model converge to the solution of the IVP for its continuum limit. These results combined with the analysis of nonlocally coupled deterministic networks in [9] justify the continuum (thermodynamic) limit for a large class of coupled dynamical systems on convergent families of graphs.
graph_limit  dynamical_system  networks 
july 2018 by rvenkat
[1302.5804] The nonlinear heat equation on dense graphs and graph limits
We use the combination of ideas and results from the theory of graph limits and nonlinear evolution equations to provide a rigorous mathematical justification for taking continuum limit for certain nonlocally coupled networks and to extend this method to cover many complex networks, for which it has not been applied before. Specifically, for dynamical networks on convergent sequences of simple and weighted graphs, we prove convergence of solutions of the initial-value problems for discrete models to those of the limiting continuous equations. In addition, for sequences of simple graphs converging to {0, 1}-valued graphons, it is shown that the convergence rate depends on the fractal dimension of the boundary of the support of the graph limit. These results are then used to study the regions of continuity of chimera states and the attractors of the nonlocal Kuramoto equation on certain multipartite graphs. Furthermore, the analytical tools developed in this work are used in the rigorous justification of the continuum limit for networks on random graphs that we undertake in a companion paper (Medvedev, 2013).
As a by-product of the analysis of the continuum limit on deterministic and random graphs, we identify the link between this problem and the convergence analysis of several classical numerical schemes: the collocation, Galerkin, and Monte-Carlo methods. Therefore, our results can be used to characterize convergence of these approximate methods of solving initial-value problems for nonlinear evolution equations with nonlocal interactions.
graph_limit  dynamical_system  networks 
july 2018 by rvenkat
[1605.02114] The semilinear heat equation on sparse random graphs
Using the theory of Lp-graphons (Borgs et al, 2014), we derive and rigorously justify the continuum limit for systems of differential equations on sparse random graphs. Specifically, we show that the solutions of the initial value problems for the discrete models can be approximated by those of an appropriate nonlocal diffusion equation. Our results apply to a range of spatially extended dynamical models of different physical, biological, social, and economic networks. Importantly, our assumptions cover network topologies featured in many important real-world networks. In particular, we derive the continuum limit for coupled dynamical systems on power law graphs. The latter is the main motivation for this work.

--See all the recent work of
http://www.math.drexel.edu/~medvedev/
graph_limit  dynamical_system  networks 
july 2018 by rvenkat
[1807.03573] Power Network Dynamics on Graphons
Power grids are undergoing major changes from a few large producers to smart grids build upon renewable energies. Mathematical models for power grid dynamics have to be adapted to capture, when dynamic nodes can achieve synchronization to a common grid frequency on complex network topologies. In this paper we study a second-order rotator model in the large network limit. We merge the recent theory of random graph limits for complex small-world networks with approaches to first-order systems on graphons. We prove that there exists a well-posed continuum limit integral equation approximating the large finite-dimensional case power grid network dynamics. Then we analyse the linear stability of synchronized solutions and prove linear stability. However, on small-world networks we demonstrate that there are topological parameters moving the spectrum arbitrarily close to the imaginary axis leading to potential instability on finite time scales.
graph_limit  dynamical_system  networks 
july 2018 by rvenkat
On the nature and use of models in network neuroscience | Nature Reviews Neuroscience
Network theory provides an intuitively appealing framework for studying relationships among interconnected brain mechanisms and their relevance to behaviour. As the space of its applications grows, so does the diversity of meanings of the term network model. This diversity can cause confusion, complicate efforts to assess model validity and efficacy, and hamper interdisciplinary collaboration. In this Review, we examine the field of network neuroscience, focusing on organizing principles that can help overcome these challenges. First, we describe the fundamental goals in constructing network models. Second, we review the most common forms of network models, which can be described parsimoniously along the following three primary dimensions: from data representations to first-principles theory; from biophysical realism to functional phenomenology; and from elementary descriptions to coarse-grained approximations. Third, we draw on biology, philosophy and other disciplines to establish validation principles for these models. We close with a discussion of opportunities to bridge model types and point to exciting frontiers for future pursuits.
review  networks  neuroscience 
july 2018 by rvenkat
[1309.6928] Structure and dynamics of core-periphery networks
Recent studies uncovered important core/periphery network structures characterizing complex sets of cooperative and competitive interactions between network nodes, be they proteins, cells, species or humans. Better characterization of the structure, dynamics and function of core/periphery networks is a key step of our understanding cellular functions, species adaptation, social and market changes. Here we summarize the current knowledge of the structure and dynamics of "traditional" core/periphery networks, rich-clubs, nested, bow-tie and onion networks. Comparing core/periphery structures with network modules, we discriminate between global and local cores. The core/periphery network organization lies in the middle of several extreme properties, such as random/condensed structures, clique/star configurations, network symmetry/asymmetry, network assortativity/disassortativity, as well as network hierarchy/anti-hierarchy. These properties of high complexity together with the large degeneracy of core pathways ensuring cooperation and providing multiple options of network flow re-channelling greatly contribute to the high robustness of complex systems. Core processes enable a coordinated response to various stimuli, decrease noise, and evolve slowly. The integrative function of network cores is an important step in the development of a large variety of complex organisms and organizations. In addition to these important features and several decades of research interest, studies on core/periphery networks still have a number of unexplored areas.
review  networks  dynamics 
july 2018 by rvenkat
[1408.6596] Emergence of Clustering in an Acquaintance Model without Homophily
We introduce an agent-based acquaintance model in which social links are created by processes in which there is no explicit homophily. In spite of the homogeneous nature of the social interactions, highly-clustered social networks can arise. The crucial feature of our model is that of variable transitive interactions. Namely, when an agent introduces two unconnected friends, the rate at which a connection actually occurs between them depends on the number of their mutual acquaintances. As this transitive interaction rate is varied, the social network undergoes a dramatic clustering transition. Close to the transition, the network consists of a collection of well-defined communities. As a function of time, the network can also undergo an \emph{incomplete} gelation transition, in which the gel, or giant cluster, does not constitute the entire network, even at infinite time. Some of the clustering properties of our model also arise, but in a more gradual manner, in Facebook networks. Finally, we discuss a more realistic variant of our original model in which there is a soft cutoff in the rate of transitive interactions. With this variant, one can construct network realizations that quantitatively match Facebook networks.
networks  teaching  sidney.redner 
july 2018 by rvenkat
Economic Consequences of Network Structure
We survey the literature on the economic consequences of the structure of social networks. We develop a taxonomy of "macro" and "micro" characteristics of social-interaction networks and discuss both the theoretical and empirical findings concerning the role of those characteristics in determining learning, diffusion, decisions, and resulting behaviors. We also discuss the challenges of accounting for the endogeneity of networks in assessing the relationship between the patterns of interactions and behaviors.
economics  social_networks  networks  review  matthew.jackson  teaching 
july 2018 by rvenkat
[1607.02441] Generalized Hypergeometric Ensembles: Statistical Hypothesis Testing in Complex Networks
Statistical ensembles of networks, i.e., probability spaces of all networks that are consistent with given aggregate statistics, have become instrumental in the analysis of complex networks. Their numerical and analytical study provides the foundation for the inference of topological patterns, the definition of network-analytic measures, as well as for model selection and statistical hypothesis testing. Contributing to the foundation of these data analysis techniques, in this Letter we introduce generalized hypergeometric ensembles, a broad class of analytically tractable statistical ensembles of finite, directed and weighted networks. This framework can be interpreted as a generalization of the classical configuration model, which is commonly used to randomly generate networks with a given degree sequence or distribution. Our generalization rests on the introduction of dyadic link propensities, which capture the degree-corrected tendencies of pairs of nodes to form edges between each other. Studying empirical and synthetic data, we show that our approach provides broad perspectives for model selection and statistical hypothesis testing in data on complex networks.
networks  statistics  network_data_analysis 
july 2018 by rvenkat
Network structure of the human musculoskeletal system shapes neural interactions on multiple time scales | Science Advances
Human motor control requires the coordination of muscle activity under the anatomical constraints imposed by the musculoskeletal system. Interactions within the central nervous system are fundamental to motor coordination, but the principles governing functional integration remain poorly understood. We used network analysis to investigate the relationship between anatomical and functional connectivity among 36 muscles. Anatomical networks were defined by the physical connections between muscles, and functional networks were based on intermuscular coherence assessed during postural tasks. We found a modular structure of functional networks that was strongly shaped by the anatomical constraints of the musculoskeletal system. Changes in postural tasks were associated with a frequency-dependent reconfiguration of the coupling between functional modules. These findings reveal distinct patterns of functional interactions between muscles involved in flexibly organizing muscle activity during postural control. Our network approach to the motor system offers a unique window into the neural circuitry driving the musculoskeletal system.
networks  dynamics  connectome 
june 2018 by rvenkat
Phys. Rev. X 8, 021071 (2018) - Key Features of Turing Systems are Determined Purely by Network Topology
Turing’s theory of pattern formation is a universal model for self-organization, applicable to many systems in physics, chemistry, and biology. Essential properties of a Turing system, such as the conditions for the existence of patterns and the mechanisms of pattern selection, are well understood in small networks. However, a general set of rules explaining how network topology determines fundamental system properties and constraints has not been found. Here we provide a first general theory of Turing network topology, which proves why three key features of a Turing system are directly determined by the topology: the type of restrictions that apply to the diffusion rates, the robustness of the system, and the phase relations of the molecular species.

--seems similar to Golubitsky's work on synchronization but ....
pattern_formation  nonlinear_dynamics  networks 
june 2018 by rvenkat
Non-assortative community structure in resting and task-evoked functional brain networks | bioRxiv
Brain networks exhibit community structure that reconfigures during cognitively demanding tasks. Extant work has emphasized a single class of communities: those that are assortative, or internally dense and externally sparse. Other classes that may play key functional roles in brain function have largely been ignored, leading to an impoverished view in the best case and a mischaracterization in the worst case. Here, we leverage weighted stochastic blockmodeling, a community detection method capable of detecting diverse classes of communities, to study the community structure of functional brain networks while subjects either rest or perform cognitively demanding tasks. We find evidence that the resting brain is largely assortative, although higher order association areas exhibit non-assortative organization, forming cores and peripheries. Surprisingly, this assortative structure breaks down during tasks and is supplanted by core, periphery, and disassortative communities. Using measures derived from the community structure, we show that it is possible to classify an individual's task state with an accuracy that is well above average. Finally, we show that inter-individual differences in the composition of assortative and non-assortative communities is correlated with subject performance on in-scanner cognitive tasks. These findings offer a new perspective on the community organization of functional brain networks and its relation to cognition.

-- for class discussions and/or student projects. Not sure about their implications... need to read more carefully.
networks  connectome  community_detection  via:clauset  teaching 
june 2018 by rvenkat
[1711.04024] How fragile are information cascades?
It is well known that sequential decision making may lead to information cascades. That is, when agents make decisions based on their private information, as well as observing the actions of those before them, then it might be rational to ignore their private signal and imitate the action of previous individuals. If the individuals are choosing between a right and a wrong state, and the initial actions are wrong, then the whole cascade will be wrong. This issue is due to the fact that cascades can be based on very little information.
We show that if agents occasionally disregard the actions of others and base their action only on their private information, then wrong cascades can be avoided. Moreover, we study the optimal asymptotic rate at which the error probability at time t can go to zero. The optimal policy is for the player at time t to follow their private information with probability pt=c/t, leading to a learning rate of c′/t, where the constants c and c′ are explicit.
self_organization  information_diffusion  contagion  decision_making  models_of_behavior  networks  ? 
june 2018 by rvenkat
Stochastic Actor-Oriented Models for Network Dynamics | Annual Review of Statistics and Its Application
This article discusses the stochastic actor-oriented model for analyzing panel data of networks. The model is defined as a continuous-time Markov chain, observed at two or more discrete time moments. It can be regarded as a generalized linear model with a large amount of missing data. Several estimation methods are discussed. After presenting the model for evolution of networks, attention is given to coevolution models. These use the same approach of a continuous-time Markov chain observed at a small number of time points, but now with an extended state space. The state space can be, for example, the combination of a network and nodal variables, or a combination of several networks. This leads to models for the dynamics of multivariate networks. The article emphasizes the approach to modeling and algorithmic issues for estimation; some attention is given to comparison with other models.
review  networks  dynamics 
june 2018 by rvenkat
[1710.07076] Core-periphery structure requires something else in the network
A network with core-periphery structure consists of core nodes that are densely interconnected. In contrast to community structure, which is a different meso-scale structure of networks, core nodes can be connected to peripheral nodes and peripheral nodes are not densely interconnected. Although core-periphery structure sounds reasonable, we argue that it is merely accounted for by heterogeneous degree distributions, if one partitions a network into a single core block and a single periphery block, which the famous Borgatti-Everett algorithm and many succeeding algorithms assume. In other words, there is a strong tendency that high-degree and low-degree nodes are judged to be core and peripheral nodes, respectively. To discuss core-periphery structure beyond the expectation of the node's degree (as described by the configuration model), we propose that one needs to assume at least one block of nodes apart from the focal core-periphery structure, such as a different core-periphery pair, community or nodes not belonging to any meso-scale structure. We propose a scalable algorithm to detect pairs of core and periphery in networks, controlling for the effect of the node's degree. We illustrate our algorithm using various empirical networks.
networks  code  network_data_analysis 
june 2018 by rvenkat
Complex Spreading Phenomena in Social Systems - Influence and Contagion in Real-World Social Networks | Sune Lehmann | Springer
This text is about spreading of information and influence in complex networks. Although previously considered similar and modeled in parallel approaches, there is now experimental evidence that epidemic and social spreading work in subtly different ways. While previously explored through modeling, there is currently an explosion of work on revealing the mechanisms underlying complex contagion based on big data and data-driven approaches.

This volume consists of four parts. Part 1 is an Introduction, providing an accessible summary of the state of the art. Part 2 provides an overview of the central theoretical developments in the field. Part 3 describes the empirical work on observing spreading processes in real-world networks. Finally, Part 4 goes into detail with recent and exciting new developments: dedicated studies designed to measure specific aspects of the spreading processes, often using randomized control trials to isolate the network effect from confounders, such as homophily.

Each contribution is authored by leading experts in the field. This volume, though based on technical selections of the most important results on complex spreading, remains quite accessible to the newly interested. The main benefit to the reader is that the topics are carefully structured to take the novice to the level of expert on the topic of social spreading processes. This book will be of great importance to a wide field: from researchers in physics, computer science, and sociology to professionals in public policy and public health.

https://socialcontagionbook.github.io/
networks  epidemics  contagion  social_networks  teaching  book 
june 2018 by rvenkat
On the history of the transportation and maximum flow problems
We review two papers that are of historical interest for combinatorial optimization: an article of A.N.Tolstoi from 1930, in which the transportation problem is studied, and a negative cycle criterion is developed and applied to solve a (for that time)large-scale (10X68) transportation problem to optimality; andan,until recently secret,RAND report of T.E.Harris and F.S. Rossfrom 1955, that Ford and Fulkerson mention as motivation to study the maximum flow problem. The papers have in common that they both apply their methods to the Soviet railway network.
networks  combinatorics  optimization  algorithms 
may 2018 by rvenkat
Internal Colonialism, Core-Periphery Contrasts and Devolution: An Integrative Comment on JSTOR
The idea of internal colonialism is presented as a framework for examining regional deprivation, especially in distinct cultural environments, and is considered in the light of the devolution debate.
economics  political_science  networks  economic_geography  economic_sociology  teaching 
may 2018 by rvenkat
Configuring Random Graph Models with Fixed Degree Sequences | SIAM Review | Vol. 60, No. 2 | Society for Industrial and Applied Mathematics
Random graph null models have found widespread application in diverse research communities analyzing network datasets, including social, information, and economic networks, as well as food webs, protein-protein interactions, and neuronal networks. The most popular random graph null models, called configuration models, are defined as uniform distributions over a space of graphs with a fixed degree sequence. Commonly, properties of an empirical network are compared to properties of an ensemble of graphs from a configuration model in order to quantify whether empirical network properties are meaningful or whether they are instead a common consequence of the particular degree sequence. In this work we study the subtle but important decisions underlying the specification of a configuration model, and we investigate the role these choices play in graph sampling procedures and a suite of applications. We place particular emphasis on the importance of specifying the appropriate graph labeling---stub-labeled or vertex-labeled---under which to consider a null model, a choice that closely connects the study of random graphs to the study of random contingency tables. We show that the choice of graph labeling is inconsequential for studies of simple graphs, but can have a significant impact on analyses of multigraphs or graphs with self-loops. The importance of these choices is demonstrated through a series of three in-depth vignettes, analyzing three different network datasets under many different configuration models and observing substantial differences in study conclusions under different models. We argue that in each case, only one of the possible configuration models is appropriate. While our work focuses on undirected static networks, it aims to guide the study of directed networks, dynamic networks, and all other network contexts that are suitably studied through the lens of random graph null models.
networks  review  simulation 
may 2018 by rvenkat
[1708.06401] A Tutorial on Hawkes Processes for Events in Social Media
This chapter provides an accessible introduction for point processes, and especially Hawkes processes, for modeling discrete, inter-dependent events over continuous time. We start by reviewing the definitions and the key concepts in point processes. We then introduce the Hawkes process, its event intensity function, as well as schemes for event simulation and parameter estimation. We also describe a practical example drawn from social media data - we show how to model retweet cascades using a Hawkes self-exciting process. We presents a design of the memory kernel, and results on estimating parameters and predicting popularity. The code and sample event data are available as an online appendix
point_process  tutorial  networks  dynamics  teaching 
april 2018 by rvenkat
[1703.10146] Community detection and stochastic block models: recent developments
The stochastic block model (SBM) is a random graph model with planted clusters. It is widely employed as a canonical model to study clustering and community detection, and provides generally a fertile ground to study the statistical and computational tradeoffs that arise in network and data sciences.
This note surveys the recent developments that establish the fundamental limits for community detection in the SBM, both with respect to information-theoretic and computational thresholds, and for various recovery requirements such as exact, partial and weak recovery (a.k.a., detection). The main results discussed are the phase transitions for exact recovery at the Chernoff-Hellinger threshold, the phase transition for weak recovery at the Kesten-Stigum threshold, the optimal distortion-SNR tradeoff for partial recovery, the learning of the SBM parameters and the gap between information-theoretic and computational thresholds.
The note also covers some of the algorithms developed in the quest of achieving the limits, in particular two-round algorithms via graph-splitting, semi-definite programming, linearized belief propagation, classical and nonbacktracking spectral methods. A few open problems are also discussed.
networks  block_model  teaching  community_detection  review 
april 2018 by rvenkat
[1804.03665] An information-theoretic, all-scales approach to comparing networks
As network research becomes more sophisticated, it is more common than ever for researchers to find themselves not studying a single network but needing to analyze sets of networks. An important task when working with sets of networks is network comparison, developing a similarity or distance measure between networks so that meaningful comparisons can be drawn. The best means to accomplish this task remains an open area of research. Here we introduce a new measure to compare networks, the Portrait Divergence, that is mathematically principled, incorporates the topological characteristics of networks at all structural scales, and is general-purpose and applicable to all types of networks. An important feature of our measure that enables many of its useful properties is that it is based on a graph invariant, the network portrait. We test our measure on both synthetic graphs and real world networks taken from protein interaction data, neuroscience, and computational social science applications. The Portrait Divergence reveals important characteristics of multilayer and temporal networks extracted from data.
graph_theory  network_data_analysis  information_theory  network_comparison  two-sample  temporal_networks  networks 
april 2018 by rvenkat
[1508.01303] Modern temporal network theory: A colloquium
The power of any kind of network approach lies in the ability to simplify a complex system so that one can better understand its function as a whole. Sometimes it is beneficial, however, to include more information than in a simple graph of only nodes and links. Adding information about times of interactions can make predictions and mechanistic understanding more accurate. The drawback, however, is that there are not so many methods available, partly because temporal networks is a relatively young field, partly because it more difficult to develop such methods compared to for static networks. In this colloquium, we review the methods to analyze and model temporal networks and processes taking place on them, focusing mainly on the last three years. This includes the spreading of infectious disease, opinions, rumors, in social networks; information packets in computer networks; various types of signaling in biology, and more. We also discuss future directions.
temporal_networks  review  networks  teaching 
april 2018 by rvenkat
[1506.08237] Dyadic data analysis with amen
Dyadic data on pairs of objects, such as relational or social network data, often exhibit strong statistical dependencies. Certain types of second-order dependencies, such as degree heterogeneity and reciprocity, can be well-represented with additive random effects models. Higher-order dependencies, such as transitivity and stochastic equivalence, can often be represented with multiplicative effects. The "amen" package for the R statistical computing environment provides estimation and inference for a class of additive and multiplicative random effects models for ordinal, continuous, binary and other types of dyadic data. The package also provides methods for missing, censored and fixed-rank nomination data, as well as longitudinal dyadic data. This tutorial illustrates the "amen" package via example statistical analyses of several of these different data types.
network_data_analysis  time_series  tensor_regression  networks  social_networks  r  packages 
april 2018 by rvenkat
[1611.00460] Inferential Approaches for Network Analyses: AMEN for Latent Factor Models
There is growing interest in the study of political networks. Network analysis allows scholars to move away from focusing on individual observations to the interrelationships among observations. Many network approaches have been developed in descriptive fashion, but attention to inferential approaches to network analysis has been growing. We introduce a new approach that models interdependencies among observations using additive and multiplicative effects (AME). This approach can be applied to binary, ordinal, and continuous network data, and provides a set of tools for inference from longitudinal networks as well. We review this approach and compare it to those examined in the recent survey by Cranmer et al. (2016). The AME approach is shown a) to be easy to implement; b) interpretable in a general linear model framework; c) computationally straightforward; d) not prone to degeneracy; e) captures 1st, 2nd, and 3rd order network dependencies; and f) notably outperforms multiple regression quadratic assignment procedures, exponential random graph models, and alternative latent space approaches on a variety of metrics and in an out-of-sample context. In summary, AME offers a straightforward way to undertake nuanced, principled inferential network analysis for a wide range of social science questions.
network_data_analysis  time_series  tensor_regression  networks  social_networks 
april 2018 by rvenkat
[1712.02497] Multiplicative Coevolution Regression Models for Longitudinal Networks and Nodal Attributes
We introduce a simple and extendable coevolution model for the analysis of longitudinal network and nodal attribute data. The model features parameters that describe three phenomena: homophily, contagion and autocorrelation of the network and nodal attribute process. Homophily here describes how changes to the network may be associated with between-node similarities in terms of their nodal attributes. Contagion refers to how node-level attributes may change depending on the network. The model we present is based upon a pair of intertwined autoregressive processes. We obtain least-squares parameter estimates for continuous-valued fully-observed network and attribute data. We also provide methods for Bayesian inference in several other cases, including ordinal network and attribute data, and models involving latent nodal attributes. These model extensions are applied to an analysis of international relations data and to data from a study of teen delinquency and friendship networks.
network_data_analysis  time_series  tensor_regression  networks  social_networks 
april 2018 by rvenkat
[1412.0048] Multilinear tensor regression for longitudinal relational data
A fundamental aspect of relational data, such as from a social network, is the possibility of dependence among the relations. In particular, the relations between members of one pair of nodes may have an effect on the relations between members of another pair. This article develops a type of regression model to estimate such effects in the context of longitudinal and multivariate relational data, or other data that can be represented in the form of a tensor. The model is based on a general multilinear tensor regression model, a special case of which is a tensor autoregression model in which the tensor of relations at one time point are parsimoniously regressed on relations from previous time points. This is done via a separable, or Kronecker-structured, regression parameter along with a separable covariance model. In the context of an analysis of longitudinal multivariate relational data, it is shown how the multilinear tensor regression model can represent patterns that often appear in relational and network data, such as reciprocity and transitivity.
network_data_analysis  time_series  tensor_regression  networks  social_networks 
april 2018 by rvenkat
[1706.09072] Influence Networks in International Relations
Measuring influence and determining what drives it are persistent questions in political science and in network analysis more generally. Herein we focus on the domain of international relations. Our major substantive question is: How can we determine what characteristics make an actor influential? To address the topic of influence, we build on a multilinear tensor regression framework (MLTR) that captures influence relationships using a tensor generalization of a vector autoregression model. Influence relationships in that approach are captured in a pair of n x n matrices and provide measurements of how the network actions of one actor may influence the future actions of another. A limitation of the MLTR and earlier latent space approaches is that there are no direct mechanisms through which to explain why a certain actor is more or less influential than others. Our new framework, social influence regression, provides a way to statistically model the influence of one actor on another as a function of characteristics of the actors. Thus we can move beyond just estimating that an actor influences another to understanding why. To highlight the utility of this approach, we apply it to studying monthly-level conflictual events between countries as measured through the Integrated Crisis Early Warning System (ICEWS) event data project.

--Convert this to a class example or HW in a future Part II of this course?

-- Data available at Dataverse but requires some preparation. Involve others (JF,PG)?

https://doi.org/10.7910/DVN/28075

-- for students in political science and international relations and ...
political_science  international_affairs  networks  teaching  network_data_analysis 
april 2018 by rvenkat
Empathy and well-being correlate with centrality in different social networks | PNAS
Individuals benefit from occupying central roles in social networks, but little is known about the psychological traits that predict centrality. Across four college freshman dorms (n = 193), we characterized individuals with a battery of personality questionnaires and also asked them to nominate dorm members with whom they had different types of relationships. This revealed several social networks within dorm communities with differing characteristics. In particular, additional data showed that networks varied in the degree to which nominations depend on (i) trust and (ii) shared fun and excitement. Networks more dependent upon trust were further defined by fewer connections than those more dependent on fun. Crucially, network and personality features interacted to predict individuals’ centrality: people high in well-being (i.e., life satisfaction and positive emotion) were central to networks characterized by fun, whereas people high in empathy were central to networks characterized by trust. Together, these findings provide network-based corroboration of psychological evidence that well-being is socially attractive, whereas empathy supports close relationships. More broadly, these data highlight how an individual’s personality relates to the roles that they play in sustaining their community.

--this one, Clauset et al hiring inequality, and Watts et al ATurk study for centrality discussion? (See also Newman and M.O.Jackson papers for theoretical discussions)
networks  teaching  network_data_analysis  matthew.jackson 
april 2018 by rvenkat
A Network Formation Model Based on Subgraphs by Arun G. Chandrasekhar, Matthew O. Jackson :: SSRN
We develop a new class of random-graph models for the statistical estimation of network formation that allow for substantial correlation in links. Various subgraphs (e.g., links, triangles, cliques, stars) are generated and their union results in a network. We provide estimation techniques for recovering the rates at which the underlying subgraphs were formed. We illustrate the models via a series of applications including testing for incentives to form cross-caste relationships in rural India, testing to see whether network structure is used to enforce risk-sharing, testing as to whether networks change in response to a community's exposure to microcredit, and show that these models significantly outperform stochastic block models in matching observed network characteristics. We also establish asymptotic properties of the models and various estimators, which requires proving a new Central Limit Theorem for correlated random variables.
networks  dynamics  teaching  social_networks  matthew.jackson 
april 2018 by rvenkat
[1405.0843] MuxViz: A Tool for Multilayer Analysis and Visualization of Networks
Multilayer relationships among entities and information about entities must be accompanied by the means to analyze, visualize, and obtain insights from such data. We present open-source software (muxViz) that contains a collection of algorithms for the analysis of multilayer networks, which are an important way to represent a large variety of complex systems throughout science and engineering. We demonstrate the ability of muxViz to analyze and interactively visualize multilayer data using empirical genetic, neuronal, and transportation networks. Our software is available at this https URL
networks  teaching  network_data_analysis  visualization  packages 
april 2018 by rvenkat
[1505.06989] A Hitting Time Formula for the Discrete Green's Function
The discrete Green's function (without boundary) G is a pseudo-inverse of the combinatorial Laplace operator of a graph G=(V,E). We reveal the intimate connection between Green's function and the theory of exact stopping rules for random walks on graphs. We give an elementary formula for Green's function in terms of state-to-state hitting times of the underlying graph. Namely, G(i,j)=πj(∑k∈VπkH(k,j)−H(i,j)) where πi is the stationary distribution at vertex i and H(i,j) is the expected hitting time for a random walk starting from vertex i to first reach vertex j. This formula also holds for the digraph Laplace operator.
The most important characteristics of a stopping rule are its exit frequencies, which are the expected number of exits of a given vertex before the rule halts the walk. We show that Green's function is, in fact, a matrix of exit frequencies plus a rank one matrix. In the undirected case, we derive spectral formulas for Green's function and for some mixing measures arising from stopping rules. Finally, we further explore the exit frequency matrix point-of-view, and discuss a natural generalization of Green's function for any distribution τ defined on the vertex set of the graph.
networks  graph_theory  probability  random_walk  combinatorics 
april 2018 by rvenkat
Lifetime-preserving reference models for characterizing spreading dynamics on temporal networks | Scientific Reports
To study how a certain network feature affects processes occurring on a temporal network, one often compares properties of the original network against those of a randomized reference model that lacks the feature in question. The randomly permuted times (PT) reference model is widely used to probe how temporal features affect spreading dynamics on temporal networks. However, PT implicitly assumes that edges and nodes are continuously active during the network sampling period – an assumption that does not always hold in real networks. We systematically analyze a recently-proposed restriction of PT that preserves node lifetimes (PTN), and a similar restriction (PTE) that also preserves edge lifetimes. We use PT, PTN, and PTE to characterize spreading dynamics on (i) synthetic networks with heterogeneous edge lifespans and tunable burstiness, and (ii) four real-world networks, including two in which nodes enter and leave the network dynamically. We find that predictions of spreading speed can change considerably with the choice of reference model. Moreover, the degree of disparity in the predictions reflects the extent of node/edge turnover, highlighting the importance of using lifetime-preserving reference models when nodes or edges are not continuously present in the network.
networks  dynamics  epidemics  temporal_networks  teaching 
april 2018 by rvenkat
Multiscale mixing patterns in networks | PNAS
Assortative mixing in networks is the tendency for nodes with the same attributes, or metadata, to link to each other. It is a property often found in social networks, manifesting as a higher tendency of links occurring between people of the same age, race, or political belief. Quantifying the level of assortativity or disassortativity (the preference of linking to nodes with different attributes) can shed light on the organization of complex networks. It is common practice to measure the level of assortativity according to the assortativity coefficient, or modularity in the case of categorical metadata. This global value is the average level of assortativity across the network and may not be a representative statistic when mixing patterns are heterogeneous. For example, a social network spanning the globe may exhibit local differences in mixing patterns as a consequence of differences in cultural norms. Here, we introduce an approach to localize this global measure so that we can describe the assortativity, across multiple scales, at the node level. Consequently, we are able to capture and qualitatively evaluate the distribution of mixing patterns in the network. We find that, for many real-world networks, the distribution of assortativity is skewed, overdispersed, and multimodal. Our method provides a clearer lens through which we can more closely examine mixing patterns in networks.
networks  homophily  spatial_statistics  social_networks 
april 2018 by rvenkat
[1803.09007] Quantifying Surveillance in the Networked Age: Node-based Intrusions and Group Privacy
From the "right to be left alone" to the "right to selective disclosure", privacy has long been thought as the control individuals have over the information they share and reveal about themselves. However, in a world that is more connected than ever, the choices of the people we interact with increasingly affect our privacy. This forces us to rethink our definition of privacy. We here formalize and study, as local and global node- and edge-observability, Bloustein's concept of group privacy. We prove edge-observability to be independent of the graph structure, while node-observability depends only on the degree distribution of the graph. We show on synthetic datasets that, for attacks spanning several hops such as those implemented by social networks and current US laws, the presence of hubs increases node-observability while a high clustering coefficient decreases it, at fixed density. We then study the edge-observability of a large real-world mobile phone dataset over a month and show that, even under the restricted two-hops rule, compromising as little as 1% of the nodes leads to observing up to 46% of all communications in the network. More worrisome, we also show that on average 36\% of each person's communications would be locally edge-observable under the same rule. Finally, we use real sensing data to show how people living in cities are vulnerable to distributed node-observability attacks. Using a smartphone app to compromise 1\% of the population, an attacker could monitor the location of more than half of London's population. Taken together, our results show that the current individual-centric approach to privacy and data protection does not encompass the realities of modern life. This makes us---as a society---vulnerable to large-scale surveillance attacks which we need to develop protections against.
networks  privacy  networked_life  social_networks 
march 2018 by rvenkat
[1803.10637] Objective measures for sentinel surveillance in network epidemiology
The problem of optimizing sentinel surveillance in networks is to find the nodes where an emerging disease outbreak can be discovered early or reliably. Whether the emphasis should be on early or reliable detection depends on the scenario in question. We investigate three objective measures quantifying the performance of nodes in sentinel surveillance the time to detection or extinction, the time to detection, and the frequency of detection. As a basis for the comparison, we use the susceptible-infectious-recovered model (SIR) on static and temporal networks of human contacts. We show that, for some regions of parameter space, the three objective measures can rank the nodes very differently. As opposed to other problems in network epidemiology, we find rather similar results for the static and temporal networks. Furthermore, we do not find one network structure that predicts the objective measures---that depends both on the data set and the SIR parameter .
networks  epidemics  contagion  signal_processing  temporal_networks 
march 2018 by rvenkat
Organization of feed-forward loop motifs reveals architectural principles in natural and engineered networks | Science Advances
Network motifs are significantly overrepresented subgraphs that have been proposed as building blocks for natural and engineered networks. Detailed functional analysis has been performed for many types of motif in isolation, but less is known about how motifs work together to perform complex tasks. To address this issue, we measure the aggregation of network motifs via methods that extract precisely how these structures are connected. Applying this approach to a broad spectrum of networked systems and focusing on the widespread feed-forward loop motif, we uncover striking differences in motif organization. The types of connection are often highly constrained, differ between domains, and clearly capture architectural principles. We show how this information can be used to effectively predict functionally important nodes in the metabolic network of Escherichia coli. Our findings have implications for understanding how networked systems are constructed from motif parts and elucidate constraints that guide their evolution.
i_remain_skeptical  networks  teaching  prediction  network_data_analysis 
march 2018 by rvenkat
[1706.00394] Multiscale unfolding of real networks by geometric renormalization
Multiple scales coexist in complex networks. However, the small world property makes them strongly entangled. This turns the elucidation of length scales and symmetries a defiant challenge. Here, we define a geometric renormalization group for complex networks and use the technique to investigate networks as viewed at different scales. We find that real networks embedded in a hidden metric space show geometric scaling, in agreement with the renormalizability of the underlying geometric model. This allows us to unfold real scale-free networks in a self-similar multilayer shell which unveils the coexisting scales and their interplay. The multiscale unfolding offers a basis for a new approach to explore critical phenomena and universality in complex networks, and affords us immediate practical applications, like high-fidelity smaller-scale replicas of large networks and a multiscale navigation protocol in hyperbolic space which boosts the success of single-layer versions.
networks  hyperbolic_geometry  phase_transition  renormalization  network_data_analysis  ? 
march 2018 by rvenkat
Conflict and convention in dynamic networks | Journal of The Royal Society Interface
An important way to resolve games of conflict (snowdrift, hawk–dove, chicken) involves adopting a convention: a correlated equilibrium that avoids any conflict between aggressive strategies. Dynamic networks allow individuals to resolve conflict via their network connections rather than changing their strategy. Exploring how behavioural strategies coevolve with social networks reveals new dynamics that can help explain the origins and robustness of conventions. Here, we model the emergence of conventions as correlated equilibria in dynamic networks. Our results show that networks have the tendency to break the symmetry between the two conventional solutions in a strongly biased way. Rather than the correlated equilibrium associated with ownership norms (play aggressive at home, not away), we usually see the opposite host–guest norm (play aggressive away, not at home) evolve on dynamic networks, a phenomenon common to human interaction. We also show that learning to avoid conflict can produce realistic network structures in a way different than preferential attachment models

-- network formation using game theory.(M.O. Jackson has a paper on a related approach). More generally, it is network formation using optimization principles.
social_networks  dynamics  norms  game_theory  networks 
march 2018 by rvenkat
Infectious Disease Modeling of Social Contagion in Networks
Many behavioral phenomena have been found to spread interpersonally through social networks, in a manner similar to infectious diseases. An important difference between social contagion and traditional infectious diseases, however, is that behavioral phenomena can be acquired by non-social mechanisms as well as through social transmission. We introduce a novel theoretical framework for studying these phenomena (the SISa model) by adapting a classic disease model to include the possibility for ‘automatic’ (or ‘spontaneous’) non-social infection. We provide an example of the use of this framework by examining the spread of obesity in the Framingham Heart Study Network. The interaction assumptions of the model are validated using longitudinal network transmission data. We find that the current rate of becoming obese is 2 per year and increases by 0.5 percentage points for each obese social contact. The rate of recovering from obesity is 4 per year, and does not depend on the number of non-obese contacts. The model predicts a long-term obesity prevalence of approximately 42, and can be used to evaluate the effect of different interventions on steady-state obesity. Model predictions quantitatively reproduce the actual historical time course for the prevalence of obesity. We find that since the 1970s, the rate of recovery from obesity has remained relatively constant, while the rates of both spontaneous infection and transmission have steadily increased over time. This suggests that the obesity epidemic may be driven by increasing rates of becoming obese, both spontaneously and transmissively, rather than by decreasing rates of losing weight. A key feature of the SISa model is its ability to characterize the relative importance of social transmission by quantitatively comparing rates of spontaneous versus contagious infection. It provides a theoretical framework for studying the interpersonal spread of any state that may also arise spontaneously, such as emotions, behaviors, health states, ideas or diseases with reservoirs.

comments from cshalizi
-----------------------

"It has recently been suggested that certain, particular types of latent homophily, in which an unobservable trait influences both which friends one chooses and current and future behavior, may be impossible to distinguish from contagion in observational studies and hence may bias estimates of contagion and homophily [50]. The circumstances under which this is likely to be a serious source of bias (e.g., whether people, empirically, behave in these sorts of ways), and what (if anything) might be done about it (absent experimental data of the kind that some new networks studies are providing [22]) merits further study. Observational data invariably pose problems for causal inference, and require one set of assumptions or another to analyze; the plausibility of these assumptions (even of standard ones that are widely used) warrants constant review.
"The SISa model as presented here assumes that all individuals have the same probability of changing state (though not everyone will actually change state within their lifetime). It is clearly possible, however, that there is heterogeneity between individuals in these rates. We do not have sufficient data on obesity in the Framingham dataset to explore this issue, which would require observing numerous transitions between states for each individual. Exploring individual differences in acquisition rate empirically is a very interesting topic for future research, as is extending the theoretical framework we introduce to take into account individual differences."

--- For "suggested", read "proved"; the second paragraph amounts to saying "Let's just agree to ignore this".
social_networks  contagion  homophily  simulation  epidemics  networks  teaching 
march 2018 by rvenkat
SocioPatterns.org
--more datasets for students, in case they are interested in dynamics, especially epidemics on networks. Includes data on temporal networks.
data_sets  contagion  epidemiology  social_networks  networks  teaching 
march 2018 by rvenkat
Social Influence and Reciprocity in Online Gift Giving – Facebook Research
Giving gifts is a fundamental part of human relationships that is being affected by technology. The Internet enables people to give at the last minute and over long distances, and to observe friends giving and receiving gifts. How online gift giving spreads in social networks is therefore important to understand. We examine 1.5 million gift exchanges on Facebook and show that receiving a gift causes individuals to be 56% more likely to give a gift in the future. Additional surveys show that online gift giving was more socially acceptable to those who learned about it by observing friends’ participation instead of a non-social encouragement. Most receivers pay the gift forward instead of reciprocating directly online, although surveys revealed additional instances of direct reciprocity, where the initial gifting occurred offline. Thus, social influence promotes the spread of online gifting, which both complements and substitutes for offline gifting.

-- something about facebook experiments and the magnitude of intervention effects make me suspicious. Maybe, I'm to reading too many of Gelman's posts.
norms  influence  contagion  online_experiments  observational_studies  social_networks  networks  teaching  i_remain_skeptical 
march 2018 by rvenkat
[1708.04575] Information flow reveals prediction limits in online social activity
Modern society depends on the flow of information over online social networks, and popular social platforms now generate significant behavioral data. Yet it remains unclear what fundamental limits may exist when using these data to predict the activities and interests of individuals. Here we apply tools from information theory to estimate the predictive information content of the writings of Twitter users and to what extent that information flows between users. Distinct temporal and social effects are visible in the information flow, and these estimates provide a fundamental bound on the predictive accuracy achievable with these data. Due to the social flow of information, we estimate that approximately 95% of the potential predictive accuracy attainable for an individual is available within the social ties of that individual only, without requiring the individual's data.

https://github.com/bagrow

--According to them, they use a version of Granger causality to measure information flow. But they never address the critiques of transfer entropies and information flows from this paper
https://arxiv.org/abs/1512.06479

The last tag applies because they do not discuss limitations of their approach, especially from Crutchfield et al point of view.
social_networks  influence  information  information_theory  networks  i_remain_skeptical 
march 2018 by rvenkat
Monophily in social networks introduces similarity among friends-of-friends | Nature Human Behaviour
The observation that individuals tend to be friends with people who are similar to themselves, commonly known as homophily, is a prominent feature of social networks. While homophily describes a bias in attribute preferences for similar others, it gives limited attention to variability. Here, we observe that attribute preferences can exhibit variation beyond what can be explained by homophily. We call this excess variation monophily to describe the presence of individuals with extreme preferences for a particular attribute possibly unrelated to their own attribute. We observe that monophily can induce a similarity among friends-of-friends without requiring any similarity among friends. To simulate homophily and monophily in synthetic networks, we propose an overdispersed extension of the classical stochastic block model. We use this model to demonstrate how homophily-based methods for predicting attributes on social networks based on friends (that is, 'the company you keep') are fundamentally different from monophily-based methods based on friends-of-friends (that is, 'the company you’re kept in'). We place particular focus on predicting gender, where homophily can be weak or non-existent in practice. These findings offer an alternative perspective on network structure and prediction, complicating the already difficult task of protecting privacy on social networks.

https://arxiv.org/abs/1705.04774
social_networks  privacy  network_data_analysis  latent_variable  block_model  via:clauset  networks  teaching  ? 
march 2018 by rvenkat
[1803.06070] Modelling sparsity, heterogeneity, reciprocity and community structure in temporal interaction data
We propose a novel class of network models for temporal dyadic interaction data. Our goal is to capture a number of important features often observed in social interactions: sparsity, degree heterogeneity, community structure and reciprocity. We propose a family of models based on self-exciting Hawkes point processes in which events depend on the history of the process. The key component is the conditional intensity function of the Hawkes Process, which captures the fact that interactions may arise as a response to past interactions (reciprocity), or due to shared interests between individuals (community structure). In order to capture the sparsity and degree heterogeneity, the base (non time dependent) part of the intensity function builds on compound random measures following Todeschini et al. (2016). We conduct experiments on a variety of real-world temporal interaction data and show that the proposed model outperforms many competing approaches for link prediction, and leads to interpretable parameters.
interating_particle_system  active_matter  temporal_networks  community_detection  networks  point_process  statistics  via:droy 
march 2018 by rvenkat
[1803.04755] Detecting sequences of system states in temporal networks
Many time-evolving systems in nature, society and technology leave traces of the interactions within them. These interactions form temporal networks that reflect the states of the systems. In this work, we pursue a coarse-grained description of these systems by proposing a method to assign discrete states to the systems and inferring the sequence of such states from the data. Such states could, for example, correspond to a mental state (as inferred from neuroimaging data) or the operational state of an organization (as inferred by interpersonal communication). Our method combines a graph distance measure and hierarchical clustering. Using several empirical data sets of social temporal networks, we show that our method is capable of inferring the system's states such as distinct activities in a school and a weekday state as opposed to a weekend state. We expect the methods to be equally useful in other settings such as temporally varying protein interactions, ecological interspecific interactions, functional connectivity in the brain and adaptive social networks.
networks  temporal_networks  time_series  interating_particle_system  ? 
march 2018 by rvenkat
Network centrality: an introduction
--This, Newman et al, and Jackson et al paper for student projects?
networks  teaching  software  python  review 
march 2018 by rvenkat
[1704.03330] Food-bridging: a new network construction to unveil the principles of cooking
In this manuscript we propose, analyse, and discuss a possible new principle behind traditional cuisine: the Food-bridging hypothesis and its comparison with the food-pairing hypothesis using the same dataset and graphical models employed in the food-pairing study by Ahn et al. [Scientific Reports, 1:196 (2011)].
The Food-bridging hypothesis assumes that if two ingredients do not share a strong molecular or empirical affinity, they may become affine through a chain of pairwise affinities. That is, in a graphical model as employed by Ahn et al., a chain represents a path that joints the two ingredients, the shortest path represents the strongest pairwise chain of affinities between the two ingredients.
Food-pairing and Food-bridging are different hypotheses that may describe possible mechanisms behind the recipes of traditional cuisines. Food-pairing intensifies flavour by mixing ingredients in a recipe with similar chemical compounds, and food-bridging smoothes contrast between ingredients. Both food-pairing and food-bridging are observed in traditional cuisines, as shown in this work.
We observed four classes of cuisines according to food-pairing and food-bridging: (1) East Asian cuisines, at one extreme, tend to avoid food-pairing as well as food-bridging; and (4) Latin American cuisines, at the other extreme, follow both principles. For the two middle classes: (2) Southeastern Asian cuisines, avoid food-pairing and follow food-bridging; and (3) Western cuisines, follow food-pairing and avoid food-bridging.
culinary_history  cultural_evolution  cooking  recipe  culinary_science  networks  teaching 
march 2018 by rvenkat
[1111.6074] Flavor network and the principles of food pairing
The cultural diversity of culinary practice, as illustrated by the variety of regional cuisines, raises the question of whether there are any general patterns that determine the ingredient combinations used in food today or principles that transcend individual tastes and recipes. We introduce a flavor network that captures the flavor compounds shared by culinary ingredients. Western cuisines show a tendency to use ingredient pairs that share many flavor compounds, supporting the so-called food pairing hypothesis. By contrast, East Asian cuisines tend to avoid compound sharing ingredients. Given the increasing availability of information on food preparation, our data-driven investigation opens new avenues towards a systematic understanding of culinary practice

http://barabasi.com/f/355.pdf

https://github.com/lingcheng99/Flavor-Network

-- my acquired expertise in cooking is going to influence my judgment of this paper.
culinary_history  cultural_evolution  cooking  recipe  culinary_science  networks  teaching 
march 2018 by rvenkat
The Network Structure of Opioid Distribution on a Darknet Cryptomarket | SpringerLink
Objectives

The current study is the first to examine the network structure of an encrypted online drug distribution network. It examines (1) the global network structure, (2) the local network structure, and (3) identifies those vendor characteristics that best explain variation in the network structure. In doing so, it evaluates the role of trust in online drug markets.
Methods

The study draws on a unique dataset of transaction level data from an encrypted online drug market. Structural measures and community detection analysis are used to characterize and investigate the network structure. Exponential random graph modeling is used to evaluate which vendor characteristics explain variation in purchasing patterns.
Results

Vendors’ trustworthiness explains more variation in the overall network structure than the affordability of vendor products or the diversity of vendor product listings. This results in a highly localized network structure with a few key vendors accounting for most transactions.
Conclusions

The results indicate that vendors’ trustworthiness is a better predictor of vendor selection than product diversity or affordability. These results illuminate the internal market dynamics that sustain digital drug markets and highlight the importance of examining how new anonymizing technologies shape global drug distribution networks.
cryptomarket  economics  crime  social_networks  ergm  networks  teaching 
march 2018 by rvenkat
Contagion on Networks 2017
-- in case I find computer savvy human geographers and epidemiologists in my class.
contagion  epidemiology  networks  teaching 
march 2018 by rvenkat
[1803.02427] Network reconstruction and error estimation with noisy network data
Most empirical studies of networks assume that the network data we are given represent a complete and accurate picture of the nodes and edges in the system of interest, but in real-world situations this is rarely the case. More often the data only specify the network structure imperfectly -- like data in essentially every other area of empirical science, network data are prone to measurement error and noise. At the same time, the data may be richer than simple network measurements, incorporating multiple measurements, weights, lengths or strengths of edges, node or edge labels, or annotations of various kinds. Here we develop a general method for making estimates of network structure and properties from any form of network data, simple or complex, when the data are unreliable, and give example applications to a selection of social and biological networks.
mark.newman  networks  teaching 
march 2018 by rvenkat
[1703.07376] Network structure from rich but noisy data
Driven by growing interest in the sciences, industry, and among the broader public, a large number of empirical studies have been conducted in recent years of the structure of networks ranging from the internet and the world wide web to biological networks and social networks. The data produced by these experiments are often rich and multimodal, yet at the same time they may contain substantial measurement error. In practice, this means that the true network structure can differ greatly from naive estimates made from the raw data, and hence that conclusions drawn from those naive estimates may be significantly in error. In this paper we describe a technique that circumvents this problem and allows us to make optimal estimates of the true structure of networks in the presence of both richly textured data and significant measurement uncertainty. We give example applications to two different social networks, one derived from face-to-face interactions and one from self-reported friendships.
mark.newman  networks  teaching 
march 2018 by rvenkat
[1709.06005] TikZ-network manual
TikZ-network is an open source software project for visualizing graphs and networks in LaTeX. It aims to provide a simple and easy tool to create, visualize and modify complex networks. The packaged is based on the PGF/TikZ languages for producing vector graphics from a geometric/algebraic description. Particular focus is made on the software usability and interoperability with other tools. Simple networks can be directly created within LaTeX, while more complex networks can be imported from external sources (e.g. igraph, networkx, QGIS, ...). Additionally, tikz-network supports visualization of multilayer networks in two and three dimensions. The software is available at: this https URL
networks  latex  teaching 
march 2018 by rvenkat
« earlier      
per page:    204080120160

related tags

?  aaron.clauset  academic  active_matter  administrative_state  algorithms  alt-right  anarchism  animal_behavior  anthropologist  anthropology  antifa  applied_math  archaelogy  artificial_intelligence  automation  bayesian  bayesian_network  behavior  bias  bibliometry  big_data  biology  block_model  blog  book  book_series  bots  brendan.nyhan  buzzfeed  c.elegans  caste_system  category_theory  causality  causal_inference  change_detection  china  cities  code  collaborative_learning  collective_action  collective_animal_behavior  collective_cognition  collective_dynamics  collective_intention  combinatorics  communism  community_detection  complexity  complex_system  computaional_advertising  computational_complexity  computational_social_science  concentration_of_measure  connectome  conspiracy_theories  contagion  contemporary_culture  cooking  course  crime  cris_moore  critique  cryptocurrency  cryptomarket  ctmc  culinary_history  culinary_science  cultural_cognition  cultural_evolution  cultural_history  cultural_market  cybersecurity  D3.js  dan.roy  dana.boyd  data  data-streams  data_analysis  data_mining  data_sets  data_visualization  debates  deborah.gordon  decision_making  democracy  diffusion  digital_humanities  discrimination  disinformation  dissent_mag  distributed_computing  dmce  duncan.watts  dynamical_system  dynamics  ecology  econometrics  economics  economic_geography  economic_sociology  emergence  epidemics  epidemiology  epidemiology_of_representations  ergm  ethics  european_politics  evolution  evolutionary_biology  evolutionary_psychology  evolution_of_cooperation  experimental_design  experimental_sociology  experiments  explanation  extremism  fascism  fb  finance  for_friends  foundations  freedom_of_expression  from_shalizi  GAFA  game_theory  genetics  geography  geometry  germany  global_politics  governance  graphical_model  graphical_models  graph_limit  graph_theory  graph_visualization  groups  higher-order_interaction  history  history_of_ideas  homophily  human_computation  hyperbolic_geometry  hypergraph  identifiability  ideology  india  inequality  influence  information  information_diffusion  information_theory  institutions  interating_particle_system  international_affairs  intervention  i_remain_skeptical  java  journalism  judgment_decision-making  jure.leskovec  kieran.healy  lab  labor  latent_variable  latex  learning  left  linear_algebra  linguistics  log-liner_model  machine_learning  mark.newman  marketing  market_failures  market_microstructure  markov_process  martin.nowak  masha.gessen  mathematics  matrix_estimation  matthew.jackson  measurement  mediation_analysis  media_studies  meta-analysis  methods  microbiome  microeconomics  migration  misinformation  models_of_behavior  moral_psychology  moral_values  multiscale_model  natural_experiment  nber  nervous_system  networked_life  networked_public_sphere  networks  network_comparison  network_data_analysis  network_inference  neural_connectivity  neuroscience  news_media  newyorker  new_media  nonlinear_dynamics  nonparametric  norms  NYTimes  observational_studies  olaf.sporns  online_experiments  operad  opinion_dynamics  optimization  p-values  packages  pattern_formation  people  percolation  phase_transition  philosophy_of_biology  philosophy_of_science  physics  platform_studies  point_process  polarization  police  political_economy  political_psychology  political_science  political_sociology  post-modern_right  poverty  prediction  privacy  probability  protests  public_goods  public_opinion  public_policy  public_sphere  python  quanta_mag  r  race  random_graph  random_matrix  random_walk  recipe  regulation  religion  renormalization  report  review  right-wing_populism  russia  science_as_a_social_process  science_technology  scientific_publishing_complex  selection  self_organization  sentiment_analysis  sidney.redner  signal_processing  silkroad  simulation  socialism  social_behavior  social_construction_of_ignorance  social_construction_of_knowledge  social_epistemology  social_influence  social_media  social_movements  social_networks  social_psychology  social_reputation  social_science  social_structure  social_theory  sociology  sociology_of_science  sociology_of_technology  software  someday  spatial_statistics  spatio-temporal_statistics  statistical_mechanics  statistics  stochastic_process  stochastic_processes  surveillance  survey  susan.athey  synchronization  teaching  temporal_networks  tensor_regression  the_atlantic  time_series  topic_model  topological_data_analysis  to_read  to_teach  tutorial  twitter  two-sample  united_states_of_america  us_congress  us_conservative_thought  us_elections  us_politics  via:?  via:clauset  via:cshalizi  via:droy  via:duncan.watts  via:henryfarrell  via:noahpinion  via:nyhan  via:strogatz  via:sunstein  via:zeynep  violence  visualization  WaPo  war  web-based_experiments  wired  zeynep.tufekci  ` 

Copy this bookmark:



description:


tags: