-
Hamiltonian Dynamics with Non-Newtonian Momentum for Rapid Sampling
Authors:
Greg Ver Steeg,
Aram Galstyan
Abstract:
Sampling from an unnormalized probability distribution is a fundamental problem in machine learning with applications including Bayesian modeling, latent factor inference, and energy-based model training. After decades of research, variations of MCMC remain the default approach to sampling despite slow convergence. Auxiliary neural models can learn to speed up MCMC, but the overhead for training t…
▽ More
Sampling from an unnormalized probability distribution is a fundamental problem in machine learning with applications including Bayesian modeling, latent factor inference, and energy-based model training. After decades of research, variations of MCMC remain the default approach to sampling despite slow convergence. Auxiliary neural models can learn to speed up MCMC, but the overhead for training the extra model can be prohibitive. We propose a fundamentally different approach to this problem via a new Hamiltonian dynamics with a non-Newtonian momentum. In contrast to MCMC approaches like Hamiltonian Monte Carlo, no stochastic step is required. Instead, the proposed deterministic dynamics in an extended state space exactly sample the target distribution, specified by an energy function, under an assumption of ergodicity. Alternatively, the dynamics can be interpreted as a normalizing flow that samples a specified energy model without training. The proposed Energy Sampling Hamiltonian (ESH) dynamics have a simple form that can be solved with existing ODE solvers, but we derive a specialized solver that exhibits much better performance. ESH dynamics converge faster than their MCMC competitors enabling faster, more stable training of neural network energy models.
△ Less
Submitted 29 December, 2021; v1 submitted 3 November, 2021;
originally announced November 2021.
-
Stacking Models for Nearly Optimal Link Prediction in Complex Networks
Authors:
Amir Ghasemian,
Homa Hosseinmardi,
Aram Galstyan,
Edoardo M. Airoldi,
Aaron Clauset
Abstract:
Most real-world networks are incompletely observed. Algorithms that can accurately predict which links are missing can dramatically speedup the collection of network data and improve the validity of network models. Many algorithms now exist for predicting missing links, given a partially observed network, but it has remained unknown whether a single best predictor exists, how link predictability v…
▽ More
Most real-world networks are incompletely observed. Algorithms that can accurately predict which links are missing can dramatically speedup the collection of network data and improve the validity of network models. Many algorithms now exist for predicting missing links, given a partially observed network, but it has remained unknown whether a single best predictor exists, how link predictability varies across methods and networks from different domains, and how close to optimality current methods are. We answer these questions by systematically evaluating 203 individual link predictor algorithms, representing three popular families of methods, applied to a large corpus of 548 structurally diverse networks from six scientific domains. We first show that individual algorithms exhibit a broad diversity of prediction errors, such that no one predictor or family is best, or worst, across all realistic inputs. We then exploit this diversity via meta-learning to construct a series of "stacked" models that combine predictors into a single algorithm. Applied to a broad range of synthetic networks, for which we may analytically calculate optimal performance, these stacked models achieve optimal or nearly optimal levels of accuracy. Applied to real-world networks, stacked models are also superior, but their accuracy varies strongly by domain, suggesting that link prediction may be fundamentally easier in social networks than in biological or technological networks. These results indicate that the state-of-the-art for link prediction comes from combining individual algorithms, which achieves nearly optimal predictions. We close with a brief discussion of limitations and opportunities for further improvement of these results.
△ Less
Submitted 17 September, 2019;
originally announced September 2019.
-
Debiasing Community Detection: The Importance of Lowly-Connected Nodes
Authors:
Ninareh Mehrabi,
Fred Morstatter,
Nanyun Peng,
Aram Galstyan
Abstract:
Community detection is an important task in social network analysis, allowing us to identify and understand the communities within the social structures. However, many community detection approaches either fail to assign low degree (or lowly-connected) users to communities, or assign them to trivially small communities that prevent them from being included in analysis. In this work, we investigate…
▽ More
Community detection is an important task in social network analysis, allowing us to identify and understand the communities within the social structures. However, many community detection approaches either fail to assign low degree (or lowly-connected) users to communities, or assign them to trivially small communities that prevent them from being included in analysis. In this work, we investigate how excluding these users can bias analysis results. We then introduce an approach that is more inclusive for lowly-connected users by incorporating them into larger groups. Experiments show that our approach outperforms the existing state-of-the-art in terms of F1 and Jaccard similarity scores while reducing the bias towards low-degree users.
△ Less
Submitted 19 March, 2019;
originally announced March 2019.
-
Coherent Compton scattering from hydrogen and helium atoms
Authors:
Irina A. Gnilozub,
Alexander Galstyan,
Yuri V. Popov,
Igor P. Volobuev
Abstract:
We develop an approach to describing coherent Compton scattering of photons in the keV energy range from hydrogen and helium atoms based on a relativistic version of the AA-approximation within the standard perturbative S-matrix formalism. The resulting formulas for the cross section take into account the effects of the electron boundness and correctly reproduce the behavior of the cross section a…
▽ More
We develop an approach to describing coherent Compton scattering of photons in the keV energy range from hydrogen and helium atoms based on a relativistic version of the AA-approximation within the standard perturbative S-matrix formalism. The resulting formulas for the cross section take into account the effects of the electron boundness and correctly reproduce the behavior of the cross section at large photon energies, where it goes to Thomson formula, which coincides with the Klein-Nishina-Tamm formula for the cross section in the non-relativistic limit.
△ Less
Submitted 24 September, 2018;
originally announced September 2018.
-
Adaptive Decision Making via Entropy Minimization
Authors:
Armen E. Allahverdyan,
Aram Galstyan,
Ali E. Abbas,
Zbigniew R. Struzik
Abstract:
An agent choosing between various actions tends to take the one with the lowest cost. But this choice is arguably too rigid (not adaptive) to be useful in complex situations, e.g., where exploration-exploitation trade-off is relevant in creative task solving or when stated preferences differ from revealed ones. Here we study an agent who is willing to sacrifice a fixed amount of expected utility f…
▽ More
An agent choosing between various actions tends to take the one with the lowest cost. But this choice is arguably too rigid (not adaptive) to be useful in complex situations, e.g., where exploration-exploitation trade-off is relevant in creative task solving or when stated preferences differ from revealed ones. Here we study an agent who is willing to sacrifice a fixed amount of expected utility for adaptation. How can/ought our agent choose an optimal (in a technical sense) mixed action? We explore consequences of making this choice via entropy minimization, which is argued to be a specific example of risk-aversion. This recovers the $ε$-greedy probabilities known in reinforcement learning. We show that the entropy minimization leads to rudimentary forms of intelligent behavior: (i) the agent assigns a non-negligible probability to costly events; but (ii) chooses with a sizable probability the action related to less cost (lesser of two evils) when confronted with two actions with comparable costs; (iii) the agent is subject to effects similar to cognitive dissonance and frustration. Neither of these features are shown by entropy maximization.
△ Less
Submitted 1 December, 2018; v1 submitted 18 March, 2018;
originally announced March 2018.
-
Memory-induced mechanism for self-sustaining activity in networks
Authors:
A. E. Allahverdyan,
G. Ver Steeg,
A. Galstyan
Abstract:
We study a mechanism of activity sustaining on networks inspired by a well-known model of neuronal dynamics. Our primary focus is the emergence of self-sustaining collective activity patterns, where no single node can stay active by itself, but the activity provided initially is sustained within the collective of interacting agents. In contrast to existing models of self-sustaining activity that a…
▽ More
We study a mechanism of activity sustaining on networks inspired by a well-known model of neuronal dynamics. Our primary focus is the emergence of self-sustaining collective activity patterns, where no single node can stay active by itself, but the activity provided initially is sustained within the collective of interacting agents. In contrast to existing models of self-sustaining activity that are caused by (long) loops present in the network, here we focus on tree--like structures and examine activation mechanisms that are due to temporal memory of the nodes. This approach is motivated by applications in social media, where long network loops are rare or absent. Our results suggest that under a weak behavioral noise, the nodes robustly split into several clusters, with partial synchronization of nodes within each cluster. We also study the randomly-weighted version of the models where the nodes are allowed to change their connection strength (this can model attention redistribution), and show that it does facilitate the self-sustained activity.
△ Less
Submitted 21 December, 2017;
originally announced December 2017.
-
Static field limit of excitation probabilities in laser-atom interactions
Authors:
A. Galstyan,
V. L. Shablov,
Yu. V. Popov,
F. Mota-Furtado,
P. F. O'Mahony,
B. Piraux
Abstract:
We consider the interaction of atomic hydrogen, in its ground state, with an electromagnetic pulse whose duration is fixed in terms of the number of optical cycles. We study the probability of excitation of the atom in the static field limit i.e. for field frequencies going to zero. Despite the fact that the well known Born-Fock adiabatic theorem is valid only for a system whose energy spectrum is…
▽ More
We consider the interaction of atomic hydrogen, in its ground state, with an electromagnetic pulse whose duration is fixed in terms of the number of optical cycles. We study the probability of excitation of the atom in the static field limit i.e. for field frequencies going to zero. Despite the fact that the well known Born-Fock adiabatic theorem is valid only for a system whose energy spectrum is discrete, we show that it is still possible to use this theorem to derive, in the low frequency limit, an analytical formula which gives the probability of transition to any excited state of the atom as a function of the field intensity, the carrier envelope phase and the number of optical cycles within the pulse. The results for the probability of excitation to low-lying excited states, obtained with this formula, agree with those we get by solving the time-dependent Schroedinger equation. The domain of validity is discussed in detail.
△ Less
Submitted 14 December, 2018; v1 submitted 30 November, 2017;
originally announced November 2017.
-
Emergence of Leadership in Communication
Authors:
Armen E. Allahverdyan,
Aram Galstyan
Abstract:
We study a neuro-inspired model that mimics a discussion (or information dissemination) process in a network of agents. During their interaction, agents redistribute activity and network weights, resulting in emergence of leader(s). The model is able to reproduce the basic scenarios of leadership known in nature and society: laissez-faire (irregular activity, weak leadership, sizable inter-followe…
▽ More
We study a neuro-inspired model that mimics a discussion (or information dissemination) process in a network of agents. During their interaction, agents redistribute activity and network weights, resulting in emergence of leader(s). The model is able to reproduce the basic scenarios of leadership known in nature and society: laissez-faire (irregular activity, weak leadership, sizable inter-follower interaction, autonomous sub-leaders); participative or democratic (strong leadership, but with feedback from followers); and autocratic (no feedback, one-way influence). Several pertinent aspects of these scenarios are found as well---e.g., hidden leadership (a hidden clique of agents driving the official autocratic leader), and successive leadership (two leaders influence followers by turns). We study how these scenarios emerge from inter-agent dynamics and how they depend on behavior rules of agents---in particular, on their inertia against state changes.
△ Less
Submitted 25 October, 2017;
originally announced October 2017.
-
Fully differential cross sections for singly ionizing 1-Mev p+He collisions at small momentum transfer: Beyond the first Born approximation
Authors:
O. Chuluunbaatar,
S. A. Zaytsev,
K. A. Kouzakov,
A. Galstyan,
V. L. Shablov,
Yu. V. Popov
Abstract:
We present calculations of the electron angular distributions in the single ionization of helium by 1-MeV proton impact at momentum transfer of 0.75 a.u. and ejected-electron energy of 6.5 eV. The results using the first and second Born approximations and the 3C model with different trial helium functions are compared to the experimental data. A good agreement between theory and experiment is foun…
▽ More
We present calculations of the electron angular distributions in the single ionization of helium by 1-MeV proton impact at momentum transfer of 0.75 a.u. and ejected-electron energy of 6.5 eV. The results using the first and second Born approximations and the 3C model with different trial helium functions are compared to the experimental data. A good agreement between theory and experiment is found in the case of the 3C final state and a strongly correlated helium wave function. The electron-electron correlations in the He atom are found to influence the ratio of the binary and recoil peak intensities.
△ Less
Submitted 1 November, 2017; v1 submitted 15 October, 2017;
originally announced October 2017.
-
Ionisation of H$_2$O by a strong ultrashort XUV pulse: a model within the single active electron approximation
Authors:
A. Galstyan,
Yu. V. Popov,
N. Janssens,
F. Mota-Furtado,
P. F. O'Mahony,
P. Decleva,
N. Quadri,
B. Piraux
Abstract:
We present and discuss a new computationally inexpensive method to study, within the single active electron approximation, the interaction of a complex system with an intense ultrashort laser pulse. As a first application, we consider the one photon single ionisation of the highest occupied molecular orbital of the water molecule by a laser pulse. The ionisation yield is calculated for different o…
▽ More
We present and discuss a new computationally inexpensive method to study, within the single active electron approximation, the interaction of a complex system with an intense ultrashort laser pulse. As a first application, we consider the one photon single ionisation of the highest occupied molecular orbital of the water molecule by a laser pulse. The ionisation yield is calculated for different orientations of the molecule with respect to the field polarization axis and for different carrier envelope phases of the pulse, and compared against predictions of another single active electron approach.
△ Less
Submitted 4 September, 2017; v1 submitted 16 March, 2017;
originally announced March 2017.
-
The strong field approximation within a Faddeev-like formalism for laser-matter interactions
Authors:
Yu. Popov,
A. Galstyan,
F. Mota-Furtado,
P. F. O'Mahony,
B. Piraux
Abstract:
We consider the interaction of atomic hydrogen with an intense laser field within the strong-field approximation. By using a Faddeev-like formalism, we introduce a new perturbative series in the binding potential of the atom. As a first test of this new approach, we calculate the electron energy spectrum in the very simple case of a photon energy higher than the ionisation potential. We show that…
▽ More
We consider the interaction of atomic hydrogen with an intense laser field within the strong-field approximation. By using a Faddeev-like formalism, we introduce a new perturbative series in the binding potential of the atom. As a first test of this new approach, we calculate the electron energy spectrum in the very simple case of a photon energy higher than the ionisation potential. We show that by contrast to the standard perturbative series in the binding potential obtained within the strong field approximation, the first terms of the new series converge rapidly towards the results we get by solving the corresponding time-dependent Schroedinger equation.
△ Less
Submitted 14 November, 2016;
originally announced November 2016.
-
Modelling laser-atom interactions in the strong field regime
Authors:
A. Galstyan,
Yu. V. Popov,
F. Mota-Furtado,
P. F. O'Mahony,
N. Janssens,
S. D. Jenkins,
O. Chuluunbaatar,
B. Piraux
Abstract:
We consider the ionisation of atomic hydrogen by a strong infrared field. We extend and study in more depth an existing semi-analytical model. Starting from the time-dependent Schroedinger equation in momentum space and in the velocity gauge we substitute the kernel of the non-local Coulomb potential by a sum of N separable potentials, each of them supporting one hydrogen bound state. This leads t…
▽ More
We consider the ionisation of atomic hydrogen by a strong infrared field. We extend and study in more depth an existing semi-analytical model. Starting from the time-dependent Schroedinger equation in momentum space and in the velocity gauge we substitute the kernel of the non-local Coulomb potential by a sum of N separable potentials, each of them supporting one hydrogen bound state. This leads to a set of N coupled one-dimensional linear Volterra integral equations to solve. We analyze the gauge problem for the model, the different ways of generating the separable potentials and establish a clear link with the strong field approximation which turns out to be a limiting case of the present model. We calculate electron energy spectra as well as the time evolution of electron wave packets in momentum space. We compare and discuss the results obtained with the model and with the strong field approximation and examine in this context, the role of excited states.
△ Less
Submitted 14 November, 2016;
originally announced November 2016.
-
Predicting online extremism, content adopters, and interaction reciprocity
Authors:
Emilio Ferrara,
Wen-Qiang Wang,
Onur Varol,
Alessandro Flammini,
Aram Galstyan
Abstract:
We present a machine learning framework that leverages a mixture of metadata, network, and temporal features to detect extremist users, and predict content adopters and interaction reciprocity in social media. We exploit a unique dataset containing millions of tweets generated by more than 25 thousand users who have been manually identified, reported, and suspended by Twitter due to their involvem…
▽ More
We present a machine learning framework that leverages a mixture of metadata, network, and temporal features to detect extremist users, and predict content adopters and interaction reciprocity in social media. We exploit a unique dataset containing millions of tweets generated by more than 25 thousand users who have been manually identified, reported, and suspended by Twitter due to their involvement with extremist campaigns. We also leverage millions of tweets generated by a random sample of 25 thousand regular users who were exposed to, or consumed, extremist content. We carry out three forecasting tasks, (i) to detect extremist users, (ii) to estimate whether regular users will adopt extremist content, and finally (iii) to predict whether users will reciprocate contacts initiated by extremists. All forecasting tasks are set up in two scenarios: a post hoc (time independent) prediction task on aggregated data, and a simulated real-time prediction task. The performance of our framework is extremely promising, yielding in the different forecasting scenarios up to 93% AUC for extremist user detection, up to 80% AUC for content adoption prediction, and finally up to 72% AUC for interaction reciprocity forecasting. We conclude by providing a thorough feature analysis that helps determine which are the emerging signals that provide predictive power in different scenarios.
△ Less
Submitted 2 May, 2016;
originally announced May 2016.
-
The DARPA Twitter Bot Challenge
Authors:
V. S. Subrahmanian,
Amos Azaria,
Skylar Durst,
Vadim Kagan,
Aram Galstyan,
Kristina Lerman,
Linhong Zhu,
Emilio Ferrara,
Alessandro Flammini,
Filippo Menczer,
Andrew Stevens,
Alexander Dekhtyar,
Shuyang Gao,
Tad Hogg,
Farshad Kooti,
Yan Liu,
Onur Varol,
Prashant Shiralkar,
Vinod Vydiswaran,
Qiaozhu Mei,
Tim Hwang
Abstract:
A number of organizations ranging from terrorist groups such as ISIS to politicians and nation states reportedly conduct explicit campaigns to influence opinion on social media, posing a risk to democratic processes. There is thus a growing need to identify and eliminate "influence bots" - realistic, automated identities that illicitly shape discussion on sites like Twitter and Facebook - before t…
▽ More
A number of organizations ranging from terrorist groups such as ISIS to politicians and nation states reportedly conduct explicit campaigns to influence opinion on social media, posing a risk to democratic processes. There is thus a growing need to identify and eliminate "influence bots" - realistic, automated identities that illicitly shape discussion on sites like Twitter and Facebook - before they get too influential. Spurred by such events, DARPA held a 4-week competition in February/March 2015 in which multiple teams supported by the DARPA Social Media in Strategic Communications program competed to identify a set of previously identified "influence bots" serving as ground truth on a specific topic within Twitter. Past work regarding influence bots often has difficulty supporting claims about accuracy, since there is limited ground truth (though some exceptions do exist [3,7]). However, with the exception of [3], no past work has looked specifically at identifying influence bots on a specific topic. This paper describes the DARPA Challenge and describes the methods used by the three top-ranked teams.
△ Less
Submitted 21 April, 2016; v1 submitted 19 January, 2016;
originally announced January 2016.
-
Reformulation of the strong field approximation for light-matter interactions
Authors:
A. Galstyan,
O. Chuluunbaatar,
A. Hamido,
Yu. V. Popov,
F. Mota-Furtado,
P. F. O'Mahony,
N. Janssens,
F. Catoire,
B. Piraux
Abstract:
We consider the interaction of hydrogen-like atoms with a strong laser field and show that the strong field approximation and all its variants may be grouped into a set of families of approximation schemes. This is done by introducing an ansatz describing the electron wave packet as the sum of the initial state wave function times a phase factor and a function which is the perturbative solution in…
▽ More
We consider the interaction of hydrogen-like atoms with a strong laser field and show that the strong field approximation and all its variants may be grouped into a set of families of approximation schemes. This is done by introducing an ansatz describing the electron wave packet as the sum of the initial state wave function times a phase factor and a function which is the perturbative solution in the Coulomb potential of an inhomogeneous time-dependent Schrödinger equation. It is the phase factor that characterizes a given family. In each of these families, the velocity and length gauge version of the approximation scheme lead to the same results at each order in the Coulomb potential. By contrast, irrespective of the gauge, approximation schemes belonging to different families give different results. Furthermore, this new formulation of the strong field approximations allows us to gain deeper insight into the validity of the strong field approximation schemes. In particular, we address two important questions: the role of the Coulomb potential in the output channel and the convergence of the perturbative series in the Coulomb potential. In all the physical situations we consider here, our results are compared to those obtained by solving numerically the time-dependent Schrödinger equation.
△ Less
Submitted 2 December, 2015;
originally announced December 2015.
-
Latent Space Model for Multi-Modal Social Data
Authors:
Yoon-Sik Cho,
Greg Ver Steeg,
Emilio Ferrara,
Aram Galstyan
Abstract:
With the emergence of social networking services, researchers enjoy the increasing availability of large-scale heterogenous datasets capturing online user interactions and behaviors. Traditional analysis of techno-social systems data has focused mainly on describing either the dynamics of social interactions, or the attributes and behaviors of the users. However, overwhelming empirical evidence su…
▽ More
With the emergence of social networking services, researchers enjoy the increasing availability of large-scale heterogenous datasets capturing online user interactions and behaviors. Traditional analysis of techno-social systems data has focused mainly on describing either the dynamics of social interactions, or the attributes and behaviors of the users. However, overwhelming empirical evidence suggests that the two dimensions affect one another, and therefore they should be jointly modeled and analyzed in a multi-modal framework. The benefits of such an approach include the ability to build better predictive models, leveraging social network information as well as user behavioral signals. To this purpose, here we propose the Constrained Latent Space Model (CLSM), a generalized framework that combines Mixed Membership Stochastic Blockmodels (MMSB) and Latent Dirichlet Allocation (LDA) incorporating a constraint that forces the latent space to concurrently describe the multiple data modalities. We derive an efficient inference algorithm based on Variational Expectation Maximization that has a computational cost linear in the size of the network, thus making it feasible to analyze massive social datasets. We validate the proposed framework on two problems: prediction of social interactions from user attributes and behaviors, and behavior prediction exploiting network information. We perform experiments with a variety of multi-modal social systems, spanning location-based social networks (Gowalla), social media services (Instagram, Orkut), e-commerce and review sites (Amazon, Ciao), and finally citation networks (Cora). The results indicate significant improvement in prediction accuracy over state of the art methods, and demonstrate the flexibility of the proposed approach for addressing a variety of different learning problems commonly occurring with multi-modal social data.
△ Less
Submitted 18 October, 2015;
originally announced October 2015.
-
Estimating Mutual Information by Local Gaussian Approximation
Authors:
Shuyang Gao,
Greg Ver Steeg,
Aram Galstyan
Abstract:
Estimating mutual information (MI) from samples is a fundamental problem in statistics, machine learning, and data analysis. Recently it was shown that a popular class of non-parametric MI estimators perform very poorly for strongly dependent variables and have sample complexity that scales exponentially with the true MI. This undesired behavior was attributed to the reliance of those estimators o…
▽ More
Estimating mutual information (MI) from samples is a fundamental problem in statistics, machine learning, and data analysis. Recently it was shown that a popular class of non-parametric MI estimators perform very poorly for strongly dependent variables and have sample complexity that scales exponentially with the true MI. This undesired behavior was attributed to the reliance of those estimators on local uniformity of the underlying (and unknown) probability density function. Here we present a novel semi-parametric estimator of mutual information, where at each sample point, densities are {\em locally} approximated by a Gaussians distribution. We demonstrate that the estimator is asymptotically unbiased. We also show that the proposed estimator has a superior performance compared to several baselines, and is able to accurately measure relationship strengths over many orders of magnitude.
△ Less
Submitted 17 February, 2016; v1 submitted 3 August, 2015;
originally announced August 2015.
-
Understanding confounding effects in linguistic coordination: an information-theoretic approach
Authors:
Shuyang Gao,
Greg Ver Steeg,
Aram Galstyan
Abstract:
We suggest an information-theoretic approach for measuring stylistic coordination in dialogues. The proposed measure has a simple predictive interpretation and can account for various confounding factors through proper conditioning. We revisit some of the previous studies that reported strong signatures of stylistic accommodation, and find that a significant part of the observed coordination can b…
▽ More
We suggest an information-theoretic approach for measuring stylistic coordination in dialogues. The proposed measure has a simple predictive interpretation and can account for various confounding factors through proper conditioning. We revisit some of the previous studies that reported strong signatures of stylistic accommodation, and find that a significant part of the observed coordination can be attributed to a simple confounding effect - length coordination. Specifically, longer utterances tend to be followed by longer responses, which gives rise to spurious correlations in the other stylistic features. We propose a test to distinguish correlations in length due to contextual factors (topic of conversation, user verbosity, etc.) and turn-by-turn coordination. We also suggest a test to identify whether stylistic coordination persists even after accounting for length coordination and contextual factors.
△ Less
Submitted 27 August, 2015; v1 submitted 1 December, 2014;
originally announced December 2014.
-
Opinion Dynamics with Confirmation Bias
Authors:
A. E. Allahverdyan,
Aram Galstyan
Abstract:
Background: Confirmation bias is the tendency to acquire or evaluate new information in a way that is consistent with one's preexisting beliefs. It is omnipresent in psychology, economics, and even scientific practices. Prior theoretical research of this phenomenon has mainly focused on its economic implications possibly missing its potential connections with broader notions of cognitive science.…
▽ More
Background: Confirmation bias is the tendency to acquire or evaluate new information in a way that is consistent with one's preexisting beliefs. It is omnipresent in psychology, economics, and even scientific practices. Prior theoretical research of this phenomenon has mainly focused on its economic implications possibly missing its potential connections with broader notions of cognitive science. Methodology/Principal Findings: We formulate a (non-Bayesian) model for revising subjective probabilistic opinion of a confirmationally-biased agent in the light of a persuasive opinion. The revision rule ensures that the agent does not react to persuasion that is either far from his current opinion or coincides with it. We demonstrate that the model accounts for the basic phenomenology of the social judgment theory, and allows to study various phenomena such as cognitive dissonance and boomerang effect. The model also displays the order of presentation effect|when consecutively exposed to two opinions, the preference is given to the last opinion (recency) or the first opinion (primacy)|and relates recency to confirmation bias. Finally, we study the model in the case of repeated persuasion and analyze its convergence properties. Conclusions: The standard Bayesian approach to probabilistic opinion revision is inadequate for describing the observed phenomenology of persuasion process. The simple non-Bayesian model proposed here does agree with this phenomenology and is capable of reproducing a spectrum of effects observed in psychology: primacy-recency phenomenon, boomerang effect and cognitive dissonance. We point out several limitations of the model that should motivate its future development.
△ Less
Submitted 16 November, 2014;
originally announced November 2014.
-
Efficient Estimation of Mutual Information for Strongly Dependent Variables
Authors:
Shuyang Gao,
Greg Ver Steeg,
Aram Galstyan
Abstract:
We demonstrate that a popular class of nonparametric mutual information (MI) estimators based on k-nearest-neighbor graphs requires number of samples that scales exponentially with the true MI. Consequently, accurate estimation of MI between two strongly dependent variables is possible only for prohibitively large sample size. This important yet overlooked shortcoming of the existing estimators is…
▽ More
We demonstrate that a popular class of nonparametric mutual information (MI) estimators based on k-nearest-neighbor graphs requires number of samples that scales exponentially with the true MI. Consequently, accurate estimation of MI between two strongly dependent variables is possible only for prohibitively large sample size. This important yet overlooked shortcoming of the existing estimators is due to their implicit reliance on local uniformity of the underlying joint distribution. We introduce a new estimator that is robust to local non-uniformity, works well with limited data, and is able to capture relationship strengths over many orders of magnitude. We demonstrate the superior performance of the proposed estimator on both synthetic and real-world data.
△ Less
Submitted 5 March, 2015; v1 submitted 7 November, 2014;
originally announced November 2014.
-
Maximally Informative Hierarchical Representations of High-Dimensional Data
Authors:
Greg Ver Steeg,
Aram Galstyan
Abstract:
We consider a set of probabilistic functions of some input variables as a representation of the inputs. We present bounds on how informative a representation is about input data. We extend these bounds to hierarchical representations so that we can quantify the contribution of each layer towards capturing the information in the original data. The special form of these bounds leads to a simple, bot…
▽ More
We consider a set of probabilistic functions of some input variables as a representation of the inputs. We present bounds on how informative a representation is about input data. We extend these bounds to hierarchical representations so that we can quantify the contribution of each layer towards capturing the information in the original data. The special form of these bounds leads to a simple, bottom-up optimization procedure to construct hierarchical representations that are also maximally informative about the data. This optimization has linear computational complexity and constant sample complexity in the number of variables. These results establish a new approach to unsupervised learning of deep representations that is both principled and practical. We demonstrate the usefulness of the approach on both synthetic and real-world data.
△ Less
Submitted 30 January, 2015; v1 submitted 27 October, 2014;
originally announced October 2014.
-
Phase Transitions in Community Detection: A Solvable Toy Model
Authors:
Greg Ver Steeg,
Cristopher Moore,
Aram Galstyan,
Armen E. Allahverdyan
Abstract:
Recently, it was shown that there is a phase transition in the community detection problem. This transition was first computed using the cavity method, and has been proved rigorously in the case of $q=2$ groups. However, analytic calculations using the cavity method are challenging since they require us to understand probability distributions of messages. We study analogous transitions in so-calle…
▽ More
Recently, it was shown that there is a phase transition in the community detection problem. This transition was first computed using the cavity method, and has been proved rigorously in the case of $q=2$ groups. However, analytic calculations using the cavity method are challenging since they require us to understand probability distributions of messages. We study analogous transitions in so-called "zero-temperature inference" model, where this distribution is supported only on the most-likely messages. Furthermore, whenever several messages are equally likely, we break the tie by choosing among them with equal probability. While the resulting analysis does not give the correct values of the thresholds, it does reproduce some of the qualitative features of the system. It predicts a first-order detectability transition whenever $q > 2$, while the finite-temperature cavity method shows that this is the case only when $q > 4$. It also has a regime analogous to the "hard but detectable" phase, where the community structure can be partially recovered, but only when the initial messages are sufficiently accurate. Finally, we study a semisupervised setting where we are given the correct labels for a fraction $ρ$ of the nodes. For $q > 2$, we find a regime where the accuracy jumps discontinuously at a critical value of $ρ$.
△ Less
Submitted 2 December, 2013;
originally announced December 2013.
-
Transfer excitation reactions in fast proton-helium collisions
Authors:
M. S. Schöffler,
H. -K. Kim,
O. Chuluunbaatar,
S. Houamer,
A. G. Galstyan,
J. N. Titze,
T. Jahnke,
L. Ph. H. Schmidt,
H. Schmidt-B"ocking,
R. D"orner,
Yu. V. Popov,
A. A. Bulychev
Abstract:
Continuing previous work, we have measured the projectile scattering-angle dependency for transfer excitation of fast protons (300-1200 keV/u) colliding with helium (p+He $\rightarrow$ H + He$^{+ *}$). Our high-resolution fully differential data are accompanied by calculations, performed in the plane wave first Born approximation and the eikonal wave Born approximation. Experimentally we find a de…
▽ More
Continuing previous work, we have measured the projectile scattering-angle dependency for transfer excitation of fast protons (300-1200 keV/u) colliding with helium (p+He $\rightarrow$ H + He$^{+ *}$). Our high-resolution fully differential data are accompanied by calculations, performed in the plane wave first Born approximation and the eikonal wave Born approximation. Experimentally we find a deep minimum in the differential cross section around 0.5 $mrad$. The comparison with our calculations shows that describing the scattering angle dependence of transfer exitation in fast collisions requires to go beyond the first Born approximation and in addition to use initial state wave function, which contains some degree of angular correlations.
△ Less
Submitted 11 March, 2014; v1 submitted 22 November, 2013;
originally announced November 2013.
-
Demystifying Information-Theoretic Clustering
Authors:
Greg Ver Steeg,
Aram Galstyan,
Fei Sha,
Simon DeDeo
Abstract:
We propose a novel method for clustering data which is grounded in information-theoretic principles and requires no parametric assumptions. Previous attempts to use information theory to define clusters in an assumption-free way are based on maximizing mutual information between data and cluster labels. We demonstrate that this intuition suffers from a fundamental conceptual flaw that causes clust…
▽ More
We propose a novel method for clustering data which is grounded in information-theoretic principles and requires no parametric assumptions. Previous attempts to use information theory to define clusters in an assumption-free way are based on maximizing mutual information between data and cluster labels. We demonstrate that this intuition suffers from a fundamental conceptual flaw that causes clustering performance to deteriorate as the amount of data increases. Instead, we return to the axiomatic foundations of information theory to define a meaningful clustering measure based on the notion of consistency under coarse-graining for finite data.
△ Less
Submitted 5 February, 2014; v1 submitted 15 October, 2013;
originally announced October 2013.
-
2D electron momentum distributions for transfer ionization in fast proton Helium collisions
Authors:
M. S. Schoeffler,
O. Chuluunbaatar,
S. Houamer,
A. G. Galstyan,
J. N. Titze,
L. Ph. H. Schmidt,
T. Jahnke,
H. Schmidt-Boecking,
R. Doerner,
Yu. V. Popov,
A. A. Gusev,
C. Dal Cappello
Abstract:
The momentum distribution of the electron in the reaction p+He $\rightarrow$ H + He$^{2+}$ + $e$ is measured for projectile energies $E_p$=300 and 630 keV/u at very small scattering angles of hydrogen. We mainly present two dimensional distributions parallel $(k_{||})$ and perpendicular $(k_{\perp})$ to the projectile beam. Theoretical calculations were carried out within the Plane Wave First Born…
▽ More
The momentum distribution of the electron in the reaction p+He $\rightarrow$ H + He$^{2+}$ + $e$ is measured for projectile energies $E_p$=300 and 630 keV/u at very small scattering angles of hydrogen. We mainly present two dimensional distributions parallel $(k_{||})$ and perpendicular $(k_{\perp})$ to the projectile beam. Theoretical calculations were carried out within the Plane Wave First Born Approximation (PWFBA), which includes both electron emission mechanisms, shake-off and sequential capture and ionization. It is shown that electron correlations in the target wave function play the most important role in the explanation of experimentally observed backward emission. Second order effects have to be involved to correctly describe the forward emission of the electron.
△ Less
Submitted 19 May, 2013;
originally announced May 2013.
-
Modeling Temporal Activity Patterns in Dynamic Social Networks
Authors:
Vasanthan Raghavan,
Greg Ver Steeg,
Aram Galstyan,
Alexander G. Tartakovsky
Abstract:
The focus of this work is on developing probabilistic models for user activity in social networks by incorporating the social network influence as perceived by the user. For this, we propose a coupled Hidden Markov Model, where each user's activity evolves according to a Markov chain with a hidden state that is influenced by the collective activity of the friends of the user. We develop generalize…
▽ More
The focus of this work is on developing probabilistic models for user activity in social networks by incorporating the social network influence as perceived by the user. For this, we propose a coupled Hidden Markov Model, where each user's activity evolves according to a Markov chain with a hidden state that is influenced by the collective activity of the friends of the user. We develop generalized Baum-Welch and Viterbi algorithms for model parameter learning and state estimation for the proposed framework. We then validate the proposed model using a significant corpus of user activity on Twitter. Our numerical studies show that with sufficient observations to ensure accurate model learning, the proposed framework explains the observed data better than either a renewal process-based model or a conventional uncoupled Hidden Markov Model. We also demonstrate the utility of the proposed approach in predicting the time to the next tweet. Finally, clustering in the model parameter space is shown to result in distinct natural clusters of users characterized by the interaction dynamic between a user and his network.
△ Less
Submitted 8 May, 2013;
originally announced May 2013.
-
Comment on "Dynamics of transfer ionization in fast ion-atom collisions"
Authors:
Yu. V. Popov,
V. L. Shablov,
K. A. Kouzakov,
A. G. Galstyan
Abstract:
We inspect the first-order electron-electron capture scenario for transfer ionization that has been recently formulated by Voitkiv et al. (Phys. Rev. A 86, 012709 (2012) and references therein). Using the multichannel scattering theory for many-body systems with Coulomb interactions, we show that this scenario is just a part of the well-studied Oppenheimer-Brinkmann-Kramers approximation. Accurate…
▽ More
We inspect the first-order electron-electron capture scenario for transfer ionization that has been recently formulated by Voitkiv et al. (Phys. Rev. A 86, 012709 (2012) and references therein). Using the multichannel scattering theory for many-body systems with Coulomb interactions, we show that this scenario is just a part of the well-studied Oppenheimer-Brinkmann-Kramers approximation. Accurate numerical calculations in this approximation for the proton-helium transfer ionization reaction exhibit no appreciable manifestation of the claimed mechanism.
△ Less
Submitted 11 August, 2013; v1 submitted 10 April, 2013;
originally announced April 2013.
-
Statistical Tests for Contagion in Observational Social Network Studies
Authors:
Greg Ver Steeg,
Aram Galstyan
Abstract:
Current tests for contagion in social network studies are vulnerable to the confounding effects of latent homophily (i.e., ties form preferentially between individuals with similar hidden traits). We demonstrate a general method to lower bound the strength of causal effects in observational social network studies, even in the presence of arbitrary, unobserved individual traits. Our tests require n…
▽ More
Current tests for contagion in social network studies are vulnerable to the confounding effects of latent homophily (i.e., ties form preferentially between individuals with similar hidden traits). We demonstrate a general method to lower bound the strength of causal effects in observational social network studies, even in the presence of arbitrary, unobserved individual traits. Our tests require no parametric assumptions and each test is associated with an algebraic proof. We demonstrate the effectiveness of our approach by correctly deducing the causal effects for examples previously shown to expose defects in existing methodology. Finally, we discuss preliminary results on data taken from the Framingham Heart Study.
△ Less
Submitted 15 April, 2013; v1 submitted 20 November, 2012;
originally announced November 2012.
-
Information-Theoretic Measures of Influence Based on Content Dynamics
Authors:
Greg Ver Steeg,
Aram Galstyan
Abstract:
The fundamental building block of social influence is for one person to elicit a response in another. Researchers measuring a "response" in social media typically depend either on detailed models of human behavior or on platform-specific cues such as re-tweets, hash tags, URLs, or mentions. Most content on social networks is difficult to model because the modes and motivation of human expression a…
▽ More
The fundamental building block of social influence is for one person to elicit a response in another. Researchers measuring a "response" in social media typically depend either on detailed models of human behavior or on platform-specific cues such as re-tweets, hash tags, URLs, or mentions. Most content on social networks is difficult to model because the modes and motivation of human expression are diverse and incompletely understood. We introduce content transfer, an information-theoretic measure with a predictive interpretation that directly quantifies the strength of the effect of one user's content on another's in a model-free way. Estimating this measure is made possible by combining recent advances in non-parametric entropy estimation with increasingly sophisticated tools for content representation. We demonstrate on Twitter data collected for thousands of users that content transfer is able to capture non-trivial, predictive relationships even for pairs of users not linked in the follower or mention graph. We suggest that this measure makes large quantities of previously under-utilized social media content accessible to rigorous statistical causal analysis.
△ Less
Submitted 15 February, 2013; v1 submitted 22 August, 2012;
originally announced August 2012.
-
Transfer ionization and its sensitivity to the ground-state wave function
Authors:
M. S. Schöffler,
O. Chuluunbaatar,
Yu. V. Popov,
S. Houamer,
J. Titze,
T. Jahnke,
L. Ph. H. Schmidt,
O. Jagutzki,
A. G. Galstyan,
A. A. Gusev
Abstract:
We present kinematically complete theoretical calculations and experiments for transfer ionization in H$^++$He collisions at 630 keV/u. Experiment and theory are compared on the most detailed level of fully differential cross sections in the momentum space. This allows us to unambiguously identify contributions from the shake-off and two-step-2 mechanisms of the reaction. It is shown that the simu…
▽ More
We present kinematically complete theoretical calculations and experiments for transfer ionization in H$^++$He collisions at 630 keV/u. Experiment and theory are compared on the most detailed level of fully differential cross sections in the momentum space. This allows us to unambiguously identify contributions from the shake-off and two-step-2 mechanisms of the reaction. It is shown that the simultaneous electron transfer and ionization is highly sensitive to the quality of a trial initial-state wave function.
△ Less
Submitted 22 February, 2013; v1 submitted 6 August, 2012;
originally announced August 2012.
-
Hidden Markov models for the activity profile of terrorist groups
Authors:
Vasanthan Raghavan,
Aram Galstyan,
Alexander G. Tartakovsky
Abstract:
The main focus of this work is on developing models for the activity profile of a terrorist group, detecting sudden spurts and downfalls in this profile, and, in general, tracking it over a period of time. Toward this goal, a $d$-state hidden Markov model (HMM) that captures the latent states underlying the dynamics of the group and thus its activity profile is developed. The simplest setting of…
▽ More
The main focus of this work is on developing models for the activity profile of a terrorist group, detecting sudden spurts and downfalls in this profile, and, in general, tracking it over a period of time. Toward this goal, a $d$-state hidden Markov model (HMM) that captures the latent states underlying the dynamics of the group and thus its activity profile is developed. The simplest setting of $d=2$ corresponds to the case where the dynamics are coarsely quantized as Active and Inactive, respectively. A state estimation strategy that exploits the underlying HMM structure is then developed for spurt detection and tracking. This strategy is shown to track even nonpersistent changes that last only for a short duration at the cost of learning the underlying model. Case studies with real terrorism data from open-source databases are provided to illustrate the performance of the proposed methodology.
△ Less
Submitted 15 January, 2014; v1 submitted 5 July, 2012;
originally announced July 2012.
-
Effects of nonzero photon momentum in (γ,2e) processes
Authors:
Alexander G. Galstyan,
Ochbadrakh Chuluunbaatar,
Yuri V. Popov,
Bernard Piraux
Abstract:
We study the effects of nonzero photon momentum on the triply-differential cross section for (γ,2e) processes. Due to the low value of the photon momentum, these effects are weak and manifest only in special kinematical conditions like the back-to-back emission of the electrons with equal energy sharing. Helium and a few light helium-like ions are treated in detail. Quite unexpectedly, the magnitu…
▽ More
We study the effects of nonzero photon momentum on the triply-differential cross section for (γ,2e) processes. Due to the low value of the photon momentum, these effects are weak and manifest only in special kinematical conditions like the back-to-back emission of the electrons with equal energy sharing. Helium and a few light helium-like ions are treated in detail. Quite unexpectedly, the magnitude of these effects is maximal for relatively small photon energies. However, although this effect on the TDCS remains rather small, of the order of a few mbarn eV^{-1} sr^{-2}, it is sufficient to be observed experimentally.
△ Less
Submitted 5 January, 2012;
originally announced January 2012.
-
Information Transfer in Social Media
Authors:
Greg Ver Steeg,
Aram Galstyan
Abstract:
Recent research has explored the increasingly important role of social media by examining the dynamics of individual and group behavior, characterizing patterns of information diffusion, and identifying influential individuals. In this paper we suggest a measure of causal relationships between nodes based on the information-theoretic notion of transfer entropy, or information transfer. This theore…
▽ More
Recent research has explored the increasingly important role of social media by examining the dynamics of individual and group behavior, characterizing patterns of information diffusion, and identifying influential individuals. In this paper we suggest a measure of causal relationships between nodes based on the information-theoretic notion of transfer entropy, or information transfer. This theoretically grounded measure is based on dynamic information, captures fine-grain notions of influence, and admits a natural, predictive interpretation. Causal networks inferred by transfer entropy can differ significantly from static friendship networks because most friendship links are not useful for predicting future dynamics. We demonstrate through analysis of synthetic and real-world data that transfer entropy reveals meaningful hidden network structures. In addition to altering our notion of who is influential, transfer entropy allows us to differentiate between weak influence over large groups and strong influence over small groups.
△ Less
Submitted 12 October, 2011;
originally announced October 2011.
-
Co-evolution of Selection and Influence in Social Networks
Authors:
Yoon-Sik Cho,
Greg Ver Steeg,
Aram Galstyan
Abstract:
Many networks are complex dynamical systems, where both attributes of nodes and topology of the network (link structure) can change with time. We propose a model of co-evolving networks where both node at- tributes and network structure evolve under mutual influence. Specifically, we consider a mixed membership stochastic blockmodel, where the probability of observing a link between two nodes depe…
▽ More
Many networks are complex dynamical systems, where both attributes of nodes and topology of the network (link structure) can change with time. We propose a model of co-evolving networks where both node at- tributes and network structure evolve under mutual influence. Specifically, we consider a mixed membership stochastic blockmodel, where the probability of observing a link between two nodes depends on their current membership vectors, while those membership vectors themselves evolve in the presence of a link between the nodes. Thus, the network is shaped by the interaction of stochastic processes describing the nodes, while the processes themselves are influenced by the changing network structure. We derive an efficient variational inference procedure for our model, and validate the model on both synthetic and real-world data.
△ Less
Submitted 14 June, 2011;
originally announced June 2011.
-
A Sequence of Relaxations Constraining Hidden Variable Models
Authors:
Greg Ver Steeg,
Aram Galstyan
Abstract:
Many widely studied graphical models with latent variables lead to nontrivial constraints on the distribution of the observed variables. Inspired by the Bell inequalities in quantum mechanics, we refer to any linear inequality whose violation rules out some latent variable model as a "hidden variable test" for that model. Our main contribution is to introduce a sequence of relaxations which provid…
▽ More
Many widely studied graphical models with latent variables lead to nontrivial constraints on the distribution of the observed variables. Inspired by the Bell inequalities in quantum mechanics, we refer to any linear inequality whose violation rules out some latent variable model as a "hidden variable test" for that model. Our main contribution is to introduce a sequence of relaxations which provides progressively tighter hidden variable tests. We demonstrate applicability to mixtures of sequences of i.i.d. variables, Bell inequalities, and homophily models in social networks. For the last, we demonstrate that our method provides a test that is able to rule out latent homophily as the sole explanation for correlations on a real social network that are known to be due to influence.
△ Less
Submitted 20 July, 2011; v1 submitted 8 June, 2011;
originally announced June 2011.
-
Statistical Mechanics of Semi-Supervised Clustering in Sparse Graphs
Authors:
Greg Ver Steeg,
Aram Galstyan,
Armen E. Allahverdyan
Abstract:
We theoretically study semi-supervised clustering in sparse graphs in the presence of pairwise constraints on the cluster assignments of nodes. We focus on bi-cluster graphs, and study the impact of semi-supervision for varying constraint density and overlap between the clusters. Recent results for unsupervised clustering in sparse graphs indicate that there is a critical ratio of within-cluster a…
▽ More
We theoretically study semi-supervised clustering in sparse graphs in the presence of pairwise constraints on the cluster assignments of nodes. We focus on bi-cluster graphs, and study the impact of semi-supervision for varying constraint density and overlap between the clusters. Recent results for unsupervised clustering in sparse graphs indicate that there is a critical ratio of within-cluster and between-cluster connectivities below which clusters cannot be recovered with better than random accuracy. The goal of this paper is to examine the impact of pairwise constraints on the clustering accuracy. Our results suggests that the addition of constraints does not provide automatic improvement over the unsupervised case. When the density of the constraints is sufficiently small, their only impact is to shift the detection threshold while preserving the criticality. Conversely, if the density of (hard) constraints is above the percolation threshold, the criticality is suppressed and the detection threshold disappears.
△ Less
Submitted 30 October, 2011; v1 submitted 21 January, 2011;
originally announced January 2011.
-
Community Detection with and without Prior Information
Authors:
Armen E. Allahverdyan,
Greg Ver Steeg,
Aram Galstyan
Abstract:
We study the problem of graph partitioning, or clustering, in sparse networks with prior information about the clusters. Specifically, we assume that for a fraction $ρ$ of the nodes their true cluster assignments are known in advance. This can be understood as a semi--supervised version of clustering, in contrast to unsupervised clustering where the only available information is the graph structur…
▽ More
We study the problem of graph partitioning, or clustering, in sparse networks with prior information about the clusters. Specifically, we assume that for a fraction $ρ$ of the nodes their true cluster assignments are known in advance. This can be understood as a semi--supervised version of clustering, in contrast to unsupervised clustering where the only available information is the graph structure. In the unsupervised case, it is known that there is a threshold of the inter--cluster connectivity beyond which clusters cannot be detected. Here we study the impact of the prior information on the detection threshold, and show that even minute [but generic] values of $ρ>0$ shift the threshold downwards to its lowest possible value. For weighted graphs we show that a small semi--supervising can be used for a non-trivial definition of communities.
△ Less
Submitted 5 October, 2010; v1 submitted 27 July, 2009;
originally announced July 2009.
-
On Maximum a Posteriori Estimation of Hidden Markov Processes
Authors:
Armen Allahverdyan,
Aram Galstyan
Abstract:
We present a theoretical analysis of Maximum a Posteriori (MAP) sequence estimation for binary symmetric hidden Markov processes. We reduce the MAP estimation to the energy minimization of an appropriately defined Ising spin model, and focus on the performance of MAP as characterized by its accuracy and the number of solutions corresponding to a typical observed sequence. It is shown that for a…
▽ More
We present a theoretical analysis of Maximum a Posteriori (MAP) sequence estimation for binary symmetric hidden Markov processes. We reduce the MAP estimation to the energy minimization of an appropriately defined Ising spin model, and focus on the performance of MAP as characterized by its accuracy and the number of solutions corresponding to a typical observed sequence. It is shown that for a finite range of sufficiently low noise levels, the solution is uniquely related to the observed sequence, while the accuracy degrades linearly with increasing the noise strength. For intermediate noise values, the accuracy is nearly noise-independent, but now there are exponentially many solutions to the estimation problem, which is reflected in non-zero ground-state entropy for the Ising model. Finally, for even larger noise intensities, the number of solutions reduces again, but the accuracy is poor. It is shown that these regimes are different thermodynamic phases of the Ising model that are related to each other via first-order phase transitions.
△ Less
Submitted 10 June, 2009;
originally announced June 2009.
-
Maximizing Influence Propagation in Networks with Community Structure
Authors:
Aram Galstyan,
Vahe Musoyan,
Paul Cohen
Abstract:
We consider the algorithmic problem of selecting a set of target nodes that cause the biggest activation cascade in a network. In case when the activation process obeys the diminishing returns property, a simple hill-climbing selection mechanism has been shown to achieve a provably good performance. Here we study models of influence propagation that exhibit critical behavior, and where the prope…
▽ More
We consider the algorithmic problem of selecting a set of target nodes that cause the biggest activation cascade in a network. In case when the activation process obeys the diminishing returns property, a simple hill-climbing selection mechanism has been shown to achieve a provably good performance. Here we study models of influence propagation that exhibit critical behavior, and where the property of diminishing returns does not hold. We demonstrate that in such systems, the structural properties of networks can play a significant role. We focus on networks with two loosely coupled communities, and show that the double-critical behavior of activation spreading in such systems has significant implications for the targeting strategies. In particular, we show that simple strategies that work well for homogeneous networks can be overly sub-optimal, and suggest simple modification for improving the performance, by taking into account the community structure.
△ Less
Submitted 7 May, 2009;
originally announced May 2009.
-
Cascading Dynamics in Modular Networks
Authors:
Aram Galstyan,
Paul Cohen
Abstract:
In this paper we study a simple cascading process in a structured heterogeneous population, namely, a network composed of two loosely coupled communities. We demonstrate that under certain conditions the cascading dynamics in such a network has a two--tiered structure that characterizes activity spreading at different rates in the communities. We study the dynamics of the model using both simula…
▽ More
In this paper we study a simple cascading process in a structured heterogeneous population, namely, a network composed of two loosely coupled communities. We demonstrate that under certain conditions the cascading dynamics in such a network has a two--tiered structure that characterizes activity spreading at different rates in the communities. We study the dynamics of the model using both simulations and an analytical approach based on annealed approximation, and obtain good agreement between the two. Our results suggest that network modularity might have implications in various applications, such as epidemiology and viral marketing.
△ Less
Submitted 13 March, 2008;
originally announced March 2008.