Search results for "Complex."
showing 10 items of 5824 documents
Quantum lower bound for inverting a permutation with advice
2014
Given a random permutation $f: [N] \to [N]$ as a black box and $y \in [N]$, we want to output $x = f^{-1}(y)$. Supplementary to our input, we are given classical advice in the form of a pre-computed data structure; this advice can depend on the permutation but \emph{not} on the input $y$. Classically, there is a data structure of size $\tilde{O}(S)$ and an algorithm that with the help of the data structure, given $f(x)$, can invert $f$ in time $\tilde{O}(T)$, for every choice of parameters $S$, $T$, such that $S\cdot T \ge N$. We prove a quantum lower bound of $T^2\cdot S \ge \tilde{\Omega}(\epsilon N)$ for quantum algorithms that invert a random permutation $f$ on an $\epsilon$ fraction of…
Statistically validated mobile communication networks: the evolution of motifs in European and Chinese data
2014
Big data open up unprecedented opportunities to investigate complex systems including the society. In particular, communication data serve as major sources for computational social sciences but they have to be cleaned and filtered as they may contain spurious information due to recording errors as well as interactions, like commercial and marketing activities, not directly related to the social network. The network constructed from communication data can only be considered as a proxy for the network of social relationships. Here we apply a systematic method, based on multiple hypothesis testing, to statistically validate the links and then construct the corresponding Bonferroni network, gen…
A comparative analysis of the statistical properties of large mobile phone calling networks.
2014
Mobile phone calling is one of the most widely used communication methods in modern society. The records of calls among mobile phone users provide us a valuable proxy for the understanding of human communication patterns embedded in social networks. Mobile phone users call each other forming a directed calling network. If only reciprocal calls are considered, we obtain an undirected mutual calling network. The preferential communication behavior between two connected users can be statistically tested and it results in two Bonferroni networks with statistically validated edges. We perform a comparative analysis of the statistical properties of these four networks, which are constructed from …
Epidemic spreading and aging in temporal networks with memory
2018
Time-varying network topologies can deeply influence dynamical processes mediated by them. Memory effects in the pattern of interactions among individuals are also known to affect how diffusive and spreading phenomena take place. In this paper we analyze the combined effect of these two ingredients on epidemic dynamics on networks. We study the susceptible-infected-susceptible (SIS) and the susceptible-infected-removed (SIR) models on the recently introduced activity-driven networks with memory. By means of an activity-based mean-field approach we derive, in the long time limit, analytical predictions for the epidemic threshold as a function of the parameters describing the distribution of …
Qualitative Comparison of Community Detection Algorithms
2011
Community detection is a very active field in complex networks analysis, consisting in identifying groups of nodes more densely interconnected relatively to the rest of the network. The existing algorithms are usually tested and compared on real-world and artificial networks, their performance being assessed through some partition similarity measure. However, artificial networks realism can be questioned, and the appropriateness of those measures is not obvious. In this study, we take advantage of recent advances concerning the characterization of community structures to tackle these questions. We first generate networks thanks to the most realistic model available to date. Their analysis r…
Detecting informative higher-order interactions in statistically validated hypergraphs
2021
Recent empirical evidence has shown that in many real-world systems, successfully represented as networks, interactions are not limited to dyads, but often involve three or more agents at a time. These data are better described by hypergraphs, where hyperlinks encode higher-order interactions among a group of nodes. In spite of the large number of works on networks, highlighting informative hyperlinks in hypergraphs obtained from real world data is still an open problem. Here we propose an analytic approach to filter hypergraphs by identifying those hyperlinks that are over-expressed with respect to a random null hypothesis, and represent the most relevant higher-order connections. We apply…
Whom to befriend to influence people
2020
Alice wants to join a new social network, and influence its members to adopt a new product or idea. Each person $v$ in the network has a certain threshold $t(v)$ for {\em activation}, i.e adoption of the product or idea. If $v$ has at least $t(v)$ activated neighbors, then $v$ will also become activated. If Alice wants to activate the entire social network, whom should she befriend? More generally, we study the problem of finding the minimum number of links that a set of external influencers should form to people in the network, in order to activate the entire social network. This {\em Minimum Links} Problem has applications in viral marketing and the study of epidemics. Its solution can be…
Elites, communities and the limited benefits of mentorship in electronic music
2020
AbstractWhile the emergence of success in creative professions, such as music, has been studied extensively, the link between individual success and collaboration is not yet fully uncovered. Here we aim to fill this gap by analyzing longitudinal data on the co-releasing and mentoring patterns of popular electronic music artists appearing in the annual Top 100 ranking of DJ Magazine. We find that while this ranking list of popularity publishes 100 names, only the top 20 is stable over time, showcasing a lock-in effect on the electronic music elite. Based on the temporal co-release network of top musicians, we extract a diverse community structure characterizing the electronic music industry.…
An Empirical Study of the Relation Between Community Structure and Transitivity
2012
One of the most prominent properties in real-world networks is the presence of a community structure, i.e. dense and loosely interconnected groups of nodes called communities. In an attempt to better understand this concept, we study the relationship between the strength of the community structure and the network transitivity (or clustering coefficient). Although intuitively appealing, this analysis was not performed before. We adopt an approach based on random models to empirically study how one property varies depending on the other. It turns out the transitivity increases with the community structure strength, and is also affected by the distribution of the community sizes. Furthermore, …
Extracting Backbones in Weighted Modular Complex Networks
2020
AbstractNetwork science provides effective tools to model and analyze complex systems. However, the increasing size of real-world networks becomes a major hurdle in order to understand their structure and topological features. Therefore, mapping the original network into a smaller one while preserving its information is an important issue. Extracting the so-called backbone of a network is a very challenging problem that is generally handled either by coarse-graining or filter-based methods. Coarse-graining methods reduce the network size by grouping similar nodes, while filter-based methods prune the network by discarding nodes or edges based on a statistical property. In this paper, we pro…