skip to main content
10.1145/1146381.1146384acmconferencesArticle/Chapter ViewAbstractPublication PagespodcConference Proceedingsconference-collections
Article

Distributed social systems

Published: 23 July 2006 Publication History

Abstract

The study of large-scale networks has emerged over the past several years as a theme that spans many disciplines, ranging from computing and information science to the social and biological sciences. Indeed, a shared interest in network structure is arguably one of the forces that is helping draw many of these disciplines closer together. As one aspect of this broader theme, we consider a convergence of ideas taking place at the boundary between distributed computer networks and human social networks --- the former consisting of computing devices linked by an underlying communication medium, and the latter consisting of people and organizations in society connected by ties that represent friendship, interaction, and influence.Distributed computing systems have long been intertwined with the social networks that link their user populations. Recent developments, however, have added further dimensions to this relationship: the growth of blogging, social networking services, and other forms of social media on the Internet have made large-scale social networks more transparent to the general public than ever before. They have also raised new research challenges at the interface of computer science and the social sciences --- challenges in which the study of distributed computing has the potential to provide considerable insight.We discuss three related areas that illustrate the issues at this interface. The first is centered around the small-world phenomenon --- the premise that most pairs of individuals in a social network are linked by very short paths (or "six degrees of separation") [36]. In earlier work, we proposed that the social-psychology experiments providing the first empirical evidence for the phenomenon [25, 35] were related in fundamental ways to the problem of decentralized routing [14], and this theme has been pursued in a number of subsequent papers (e.g. [5, 8, 15, 17, 24, 29, 31, 32]). This line of research has helped to abstract some of the general principles underlying random graphs in which decentralized routing and search are feasible --- structures in which local information is sufficient to reach designated targets in the network. In the process, close connections have been developed to research in the design of decentralized peer-to-peer systems [3, 20, 21, 22, 23], and some of the patterns suggested by the basic models of small-world networks have been borne out to a striking extent by empirical studies of social network structure [2, 19].As a second area, we consider cascading behavior and the diffusion of information in networks. Rumors, fads, innovations, social movements, and diseases spread through human social networks [9, 28, 30, 33] in much the way that information propagates through a distributed system. And as with small-world networks, the analogies between the computational and social versions of these phenomena turn out to be deep rather than superficial. One of the oldest connections here was the pioneering work on epidemic algorithms presented by Demers et al. at PODC 1987 [6], in which probabilistic rules for information dissemination in distributed systems are modeled on aspects of biological epidemics (see [12] for a recent overview of this topic). Recent work has exploited similar analogies in the development of viral marketing strategies to promote new innovations by word-of-mouth effects [7, 13, 18, 27], in the growth of on-line communities and social networking sites [4], and in the analysis of information cascades among weblogs [1, 10].Finally, we consider game-theoretic models for these types of search and diffusion processes. The use of game theory to analyze networks of interacting strategic agents has become an active area of research in computer science (see e.g. [11, 26, 34]); in the present context we can ask how the introduction of economic incentives affects the performance of decentralized search or information diffusion algorithms. In particular, if the intermediaries on a path from a query to an answer require compensation for their participation in the search, then the dynamics of the system depend crucially on both the structure of the network and on the rarity of the answer; the resulting analysis leads to natural questions related to strategic behavior in branching processes [16].

References

[1]
L. Adamic, E. Adar. How to search a social network. Social Networks, 27(3):187--203, July 2005.
[2]
E. Adar, L. Zhang, L. A. Adamic, R. M. Lukose. "Implicit Structure and the Dynamics of Blogspace." Workshop on the Weblogging Ecosystem, at the International WWW Conference, 2004.
[3]
J. Aspnes, G. Shah. Distributed data structures for P2P systems. in Theoretical and Algorithmic Aspects of Sensor, Ad Hoc Wireless and Peer-to-Peer Networks (Jie Wu, ed.), CRC Press, 2005.
[4]
L. Backstrom, D. Huttenlocher, J. Kleinberg, X. Lan. Group Formation in Large Social Networks: Membership, Growth, and Evolution. Proc. 12th ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining, 2006.
[5]
L. Barrière, P. Fraigniaud, E. Kranakis, D. Krizanc. Efficient Routing in Networks with Long Range Contacts. Proceedings of DISC 2001.
[6]
A. Demers, D. Greene, C. Hauser, W. Irish, J. Larson, S. Shenker, H. Stuygis, D. Swinehart, D. Terry, Epidemic algorithms for replicated database maintenance. Proc. ACM Symp. on Principles of Distributed Computing, 1987.
[7]
P. Domingos, M. Richardson. Mining the Network Value of Customers. Seventh International Conference on Knowledge Discovery and Data Mining, 2001.
[8]
P. Fraigniaud, C. Gavoille, and C. Paul. Eclecticism shrinks even small worlds. Proceedings of 23rd Annual Symposium on Principles of Distributed Computing, 2004.
[9]
M. Granovetter. Threshold models of collective behavior. American Journal of Sociology 83(6):1420--1443, 1978.
[10]
D. Gruhl, R. Guha, D. Liben-Nowell, A. Tomkins. "Information Diffusion through Blogspace." Proc. International WWW Conference, 2004.
[11]
S. Kakade, M. Kearns, L. Ortiz, R. Pemantle and S. Suri. Economic Properties of Social Networks. Proc. NIPS, 2004.
[12]
D. Kempe, Gossip and Information Flow in Networks. Ph.D. thesis, Cornell University, 2003.
[13]
D. Kempe, J. Kleinberg, E. Tardos. Maximizing the Spread of Influence through a Social Network. Proc. Ninth ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining, 2003.
[14]
J. Kleinberg. The small-world phenomenon: An algorithmic perspective. Proc. 32nd ACM Symposium on Theory of Computing, 2000.
[15]
J. Kleinberg. Complex Networks and Decentralized Search Algorithms. Proceedings of the International Congress of Mathematicians (ICM), 2006.
[16]
J. Kleinberg, P. Raghavan. Query Incentive Networks. Proc. IEEE Symposium on Foundations of Computer Science, 2005.
[17]
E. Lebhar, N. Schabanel, Almost optimal decentralized routing in long-range contact networks, Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP), 2004.
[18]
J. Leskovec, A. Singh, J. Kleinberg. Patterns of Influence in a Recommendation Network. Proc. Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD), 2006.
[19]
D. Liben-Nowell, J. Novak, R. Kumar, P. Raghavan, A. Tomkins. Geographic routing in social networks. Proc. Natl. Acad. Sci. USA, 102(Aug 2005).
[20]
E-K Lua, J. Crowcroft, M. Pias, R. Sharma and S. Lim. A Survey and Comparison of Peer-to-Peer Overlay Network Schemes, IEEE Communications Surveys and Tutorials, 7(2005).
[21]
D. Malkhi, M. Naor, D. Ratajczak. Viceroy: a scalable and dynamic emulation of the butterfly. Proceedings of 21st Annual Symposium on Principles of Distributed Computing, 2002.
[22]
G. S. Manku, M. Bawa, P. Raghavan. Symphony: Distributed hashing in a small world. Proc. 4th USENIX Symposium on Internet Technologies and Systems, 2003.
[23]
G. Manku, M. Naor, and U. Wieder. Know Thy Neighbor's Neighbor: The Power of Lookahead in Randomized P2P Networks. Proc. of ACM Symp. on Theory of Computing (STOC), 2004.
[24]
C. Martel, V. Nguyen. Analyzing Kleinberg's (and other) small-world models. Proceedings of 23rd ACM Symposium on Principles of Distributed Computing, 2004.
[25]
S. Milgram, The small world problem. Psychology Today 1(1967).
[26]
C. H. Papadimitriou. Algorithms, Games, and the Internet. Proc. 33rd ACM Symposium on Theory of Computing, 2001.
[27]
M. Richardson, P. Domingos. Mining Knowledge-Sharing Sites for Viral Marketing. Eighth Intl. Conf. on Knowledge Discovery and Data Mining, 2002.
[28]
E. Rogers. Diffusion of innovations Free Press, 1995.
[29]
O. Sandberg. Searching a Small World. Licentiate thesis, Chalmers University, 2005.
[30]
T. Schelling. Micromotives and Macrobehavior. Norton, 1978.
[31]
O. Simsek and D. Jensen. Decentralized search in networks using homophily and degree disparity. Proc. 19th International Joint Conference on Artificial Intelligence, 2005.
[32]
A. Slivkins. Distance Estimation and Object Location via Rings of Neighbors. Proceedings of 24th Annual Symposium on Principles of Distributed Computing, 2005.
[33]
D. Strang, S. Soule. Diffusion in Organizations and Social Movements: From Hybrid Corn to Poison Pills. Ann. Rev. Sociology 24(1998), pp. 265--290.
[34]
É. Tardos. Network Games. Proc. 36th ACM Symposium on Theory of Computing, 2004.
[35]
J. Travers and S. Milgram. An experimental study of the small world problem. Sociometry 32(1969).
[36]
Duncan J. Watts. Six Degrees: The Science of a Connected Age, W. W. Norton, 2003.

Cited By

View all
  • (2010)Making the invisible visible through social network analysis2010 International Conference on Information Retrieval & Knowledge Management (CAMP)10.1109/INFRKM.2010.5466883(11-17)Online publication date: Mar-2010
  • (2009)A brief survey of computational approaches in social computingProceedings of the 2009 international joint conference on Neural Networks10.5555/1704555.1704660(2699-2706)Online publication date: 14-Jun-2009
  • (2009)A brief survey of computational approaches in Social Computing2009 International Joint Conference on Neural Networks10.1109/IJCNN.2009.5178967(1625-1632)Online publication date: Jun-2009

Index Terms

  1. Distributed social systems

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    PODC '06: Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing
    July 2006
    230 pages
    ISBN:1595933840
    DOI:10.1145/1146381
    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

    Sponsors

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 23 July 2006

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. algorithmic game theory
    2. distributed systems
    3. small-world phenomenon
    4. social networks

    Qualifiers

    • Article

    Conference

    PODC06

    Acceptance Rates

    Overall Acceptance Rate 740 of 2,477 submissions, 30%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)5
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 14 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2010)Making the invisible visible through social network analysis2010 International Conference on Information Retrieval & Knowledge Management (CAMP)10.1109/INFRKM.2010.5466883(11-17)Online publication date: Mar-2010
    • (2009)A brief survey of computational approaches in social computingProceedings of the 2009 international joint conference on Neural Networks10.5555/1704555.1704660(2699-2706)Online publication date: 14-Jun-2009
    • (2009)A brief survey of computational approaches in Social Computing2009 International Joint Conference on Neural Networks10.1109/IJCNN.2009.5178967(1625-1632)Online publication date: Jun-2009

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media