On the Dynamics of Social Balance on General Networks (with an application to XOR-SAT)

• Autorzy: Istrate G.
• Języki publikacji: EN

Abstrakty

EN

We study nondeterministic and probabilistic versions of a discrete dynamical system (due to T. Antal, P. L. Krapivsky, and S. Redner [3]) inspired by Heider’s social balance theory. We investigate the convergence time of this dynamics on several classes of graphs. Our contributions include: 1. We point out the connection between the triad dynamics and a generalization of annihilating walks to hypergraphs. In particular, this connection allows us to completely characterize the recurrent states in graphs where each edge belongs to at most two triangles. 2. We also solve the case of hypergraphs that do not contain edges consisting of one or two vertices. 3. We show that on the so-called "triadic cycle"graph, the convergence time is linear. 4. We obtain a cubic upper bound on the convergence time on 2-regular triadic simplexes G. This bound can be further improved to a quantity that depends on the Cheeger constant of G. In particular this provides some rigorous counterparts to experimental observations in [25]. We also point out an application to the analysis of the random walk algorithm on certain instances of the 3-XOR-SAT problem.

Słowa kluczowe

EN

social balance; discrete dynamical system; rapidly mixingMarkov chains; XOR-SAT

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2009
• Tom: Vol. 91, nr 2
• Strony: 341--356
• Opis fizyczny: Bibliogr. 29 poz., wykr.

Twórcy

autor

Istrate G.

• Austria Research Institute, Bd. V. P�arvan 4, cam. 045B, Timisoara RO-300223, Romania,

Bibliografia

• [1] Aldous, D.: Meeting times for independentMarkov chains, Stochastic Processes and their applications, 38, 1991, 185-193.
• [2] Aldous, D., Fill, A.: Reversible Markov Chains and Random Walks on Graphs, (manuscript in preparation), Available from http://www.stat.berkeley.edu/ aldous/RWG/book.html, 2007.
• [3] Antal, T., Krapivsky, P. L., Redner, S.: Social Balance on Networks: The Dynamics of Friendship and Enmity, Physica D, 224(130), 2006.
• [4] Barrett, C., Bisset, K., Eubank, S., Kumar, V. A., Marathe, M., Mortveit, H.: Modeling and Simulation of Large Biological, Information and Socio-Technical Systems: An Interaction-Based Approach, Proceedings of the Short Course on Modeling and Simulation of Biological Networks, AMS Lecture Notes, Springer Verlag, 2006.
• [5] Barrett, C., Hunt, H.,Marathe,M., Ravi, S., Rosenkrantz, D., Stearns, R.: Reachability Problems for Sequential Dynamical Systems with Threshold Functions, Theoretical Computer Science, 295(1-3), 2003, 41-64.
• [6] Barrett, C., Hunt, H., Marathe, M., Ravi, S., Rosenkrantz, D., Stearns, R.: Complexity of reachability problems for finite discrete dynamical systems, Journal of Computer and System Sciences, 72(8), 2006, 1317-1345.
• [7] Barthel, W., Hartmann, A., Weigt, M.: Solving satisfiability problems by fluctuations: The dynamics of stochastic local search algorithms, Phys. Rev. E, 67(066104), 2003.
• [8] Braunstein, A., Mézard, M., Zecchina, R.: Survey propagation: an algorithm for satisfiability, Random Structures and Algorithms, 27(2), 2005, 201-226.
• [9] Cartwright, D., Harary, F.: Structural balance: a generalization of Heider's theory, Psychological Review, 63, 1956, 277-293.
• [10] Donnelly, P., Welsh, D.: Finite particle systems and infection models, Math.Proc. Cambridge Philos.Soc., 94, 1983, 167-182.
• [11] Dubois, O., Mandler, J.: The 3-XORSAT threshold, C. R. Math. Acad. Sci. Paris, 335(11), 2002, 963-966, ISSN 1631-073X.
• [12] Dyer, M., Greenhill, C., Goldberg, L., Istrate, G., Jerrum, M.: The Convergence of Iterated Prisoner's Dilemma Game, Combinatorics, Probability and Computing, 11, 2002, 135-147.
• [13] Erdős, P., Ney, P.: Some problems on random intervals and annihilating particles, Annals of Probability, 2, 1974, 828-839.
• [14] Griffeath, D.: Additive and Cancellative Interactive Particle Systems, Springer Verlag, 1979.
• [15] Grünbaum, B., Shephard, G.: Tilings and patterns, W.H. Freeman & co., 1986.
• [16] Hegselmann, R., Flache, A.: Understanding Complex Social Dynamics: A Plea For Cellular Automata Based Modelling, Journal of Artificial Societies and Social Simulation, 1(3), 1998.
• [17] Heider, F.: The psychology of interpersonal relations, JohnWiley & Sons, 1958.
• [18] Hummon, N., Doreian, P.: Some dynamics of social balance processes: bringing Heider back into balance theory, Social Networks, 25(1), 2003, 17-49.
• [19] Ilachinski, A.: Cellular Automata: A Discrete Universe, World Scientific, 2001.
• [20] Kulakowski, K.: Some Recent Attempts to Simulate the Heider Balance Problem, Computing in Science and Engineering, 9(4), 2007, 80-85, ISSN 1521-9615.
• [21] Kulakowski, K., Gawronski, P., Gronek, P.: The Heider balance - a continuous approach, International Journal of Modern Physics C, 16, 2005, 707.
• [22] Mortveit, H., Reydis, C.: An Introduction to Sequential Dynamical Systems, Springer Verlag, 2007.
• [23] Mossel, E., Roch, S.: Slow Emergence of Cooperation forWin-Stay Lose-Shift on Trees, Machine Learning, 7(1-2), 2006, 7-22.
• [24] Motwani, R., Raghavan, P.: Randomized Algorithms, Cambridge University Press, 1995.
• [25] Radicchi, F., Vilone, D., Meyer-Ortmanns, H.: Universal Class of Triad Dynamics on a Triangular Lattice, Physical Review E, 021118, 2006.
• [26] Radicchi, F., Vilone, D., Yoon, S., Meyer-Ortmanns, H.: Social balance as a satisfiability problem of computer science, Physical Review E, 026106, 2006.
• [27] Ricci-Tersenghi, F., Weight, M., Zecchina, R.: Simplest random k-satisfiability problem, Physical Reviews E, 63, 2001, 026702.
• [28] Semerjian, G., Monasson, R.: Relaxation and Metastability in a local search procedure for the random satisfiability problem, Phys. Rev. E, 67(066103), 2003.
• [29] Wang, Z., Thorngate,W.: Sentiment and social mitosis: Implications of Heider's Balance Theory, Journal of Artificial Societies and Social Simulation, 6(3), 2003.