Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe Iterated Local Model for Social Networks
81
0
0.0
(
0
)
Added by
Anthony Bonato
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
On-line social networks, such as in Facebook and Twitter, are often studied from the perspective of friendship ties between agents in the network. Adversarial ties, however, also play an important role in the structure and function of social networks, but are often hidden. Underlying generative mechanisms of social networks are predicted by structural balance theory, which postulates that triads of agents, prefer to be transitive, where friends of friends are more likely friends, or anti-transitive, where adversaries of adversaries become friends. The previously proposed Iterated Local Transitivity (ILT) and Iterated Local Anti-Transitivity (ILAT) models incorporated transitivity and anti-transitivity, respectively, as evolutionary mechanisms. These models resulted in graphs with many observable properties of social networks, such as low diameter, high clustering, and densification. We propose a new, generative model, referred to as the Iterated Local Model (ILM) for social networks synthesizing both transitive and anti-transitive triads over time. In ILM, we are given a countably infinite binary sequence as input, and that sequence determines whether we apply a transitive or an anti-transitive step. The resulting model exhibits many properties of complex networks observed in the ILT and ILAT models. In particular, for any input binary sequence, we show that asymptotically the model generates finite graphs that densify, have clustering coefficient bounded away from 0, have diameter at most 3, and exhibit bad spectral expansion. We also give a thorough analysis of the chromatic number, domination number, Hamiltonicity, and isomorphism types of induced subgraphs of ILM graphs.
rate research
Read More
We study a model of opinion exchange in social networks where a state of the world is realized and every agent receives a zero-mean noisy signal of the realized state. It is known from Golub and Jackson that under the DeGroot dynamics agents reach a consensus which is close to the state of the world when the network is large. The DeGroot dynamics, however, is highly non-robust and the presence of a single `bot that does not adhere to the updating rule, can sway the public consensus to any other value. We introduce a variant of the DeGroot dynamics which we call emph{ $varepsilon$-DeGroot}. The $varepsilon$-DeGroot dynamics approximates the standard DeGroot dynamics and like the DeGroot dynamics it is Markovian and stationary. We show that in contrast to the standard DeGroot dynamics, the $varepsilon$-DeGroot dynamics is highly robust both to the presence of bots and to certain types of misspecifications.
Let $G$ be a directed graph such that the in-degree of any vertex $G$ is at least one. Let also ${mathcal{tau}}: V(G)rightarrow Bbb{N}$ be an assignment of thresholds to the vertices of $G$. A subset $M$ of vertices of $G$ is called a dynamic monopoly for $(G,tau)$ if the vertex set of $G$ can be partitioned into $D_0cup... cup D_t$ such that $D_0=M$ and for any $igeq 1$ and any $vin D_i$, the number of edges from $D_0cup... cup D_{i-1}$ to $v$ is at least $tau(v)$. One of the most applicable and widely studied threshold assignments in directed graphs is strict majority threshold assignment in which for any vertex $v$, $tau(v)=lceil (deg^{in}(v)+1)/2 rceil$, where $deg^{in}(v)$ stands for the in-degree of $v$. By a strict majority dynamic monopoly of a graph $G$ we mean any dynamic monopoly of $G$ with strict majority threshold assignment for the vertices of $G$. In this paper we first discuss some basic upper and lower bounds for the size of dynamic monopolies with general threshold assignments and then obtain some hardness complexity results concerning the smallest size of dynamic monopolies in directed graphs. Next we show that any directed graph on $n$ vertices and with positive minimum in-degree admits a strict majority dynamic monopoly with $n/2$ vertices. We show that this bound is achieved by a polynomial time algorithm. This upper bound improves greatly the best known result. The final note of the paper deals with the possibility of the improvement of the latter $n/2$ bound.
In this paper, we propose a generalized opinion dynamics model (GODM), which can dynamically compute each persons expressed opinion, to solve the internal opinion maximization problem for social trust networks. In the model, we propose a new, reasonable and interpretable confidence index, which is determined by both persons social status and the evaluation around him. By using the theory of diagonally dominant, we obtain the optimal analytic solution of the Nash equilibrium with maximum overall opinion. We design a novel algorithm to maximize the overall with given budget by modifying the internal opinions of people in the social trust network, and prove its optimality both from the algorithm itself and the traditional optimization algorithm-ADMM algorithms with $l_1$-regulations. A series of experiments are conducted, and the experimental results show that our method is superior to the state-of-the-art in four datasets. The average benefit has promoted $67.5%$, $83.2%$, $31.5%$, and $33.7%$ on four datasets, respectively.
For generalized Dyck paths (i.e., directed lattice paths with any finite set of jumps), we analyse their local time at zero (i.e., the number of times the path is touching or crossing the abscissa). As we are in a discrete setting, the event we analyse here is invisible to the tools of Brownian motion theory. It is interesting that the key tool for analysing directed lattice paths, which is the kernel method, is not directly applicable here. Therefore, we introduce a variant of this kernel method to get the trivariate generating function (length, final altitude, local time): this leads to an expression involving symmetric and algebraic functions. We apply this analysis to different types of constrained lattice paths (meanders , excursions, bridges,. . .). Then, we illustrate this approach on basketball walks which are walks defined by the jumps --2, --1, 0, +1, +2. We use singularity analysis to prove that the limit laws for the local time are (depending on the drift and the type of walk) the geometric distribution, the negative binomial distribution, the Rayleigh distribution, or the half-normal distribution (a universal distribution up to now rarely encountered in analytic combinatorics).
Numerical analysis of data from international trade and ecological networks has shown that the non-linear fitness-complexity metric is the best candidate to rank nodes by importance in bipartite networks that exhibit a nested structure. Despite its relevance for real networks, the mathematical properties of the metric and its variants remain largely unexplored. Here, we perform an analytic and numeric study of the fitness-complexity metric and a new variant, called minimal extremal metric. We rigorously derive exact expressions for node scores for perfectly nested networks and show that these expressions explain the non-trivial convergence properties of the metrics. A comparison between the fitness-complexity metric and the minimal extremal metric on real data reveals that the latter can produce improved rankings if the input data are reliable.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
