  We study a majority based preference diffusion model in which the members of
a social network update their preferences based on those of their connections.
Consider an undirected graph where each node has a strict linear order over a
set of $\alpha$ alternatives. At each round, a node randomly selects two
adjacent alternatives and updates their relative order with the majority view
of its neighbors. We bound the convergence time of the process in terms of the
number of nodes/edges and $\alpha$. Furthermore, we study the minimum cost to
ensure that a desired alternative will ``win'' the process, where occupying
each position in a preference order of a node has a cost. We prove tight bounds
on the minimum cost for general graphs and graphs with strong expansion
properties. Furthermore, we investigate a more light-weight process where each
node chooses one of its neighbors uniformly at random and copies its order
fully with some fixed probability and remains unchanged otherwise. We
characterize the convergence properties of this process, namely convergence
time and stable states, using Martingale and reversible Markov chain analysis.
Finally, we present the outcomes of our experiments conducted on different
synthetic random graph models and graph data from online social platforms.
These experiments not only support our theoretical findings, but also shed some
light on some other fundamental problems, such as designing powerful
countermeasures.
