CiteULike: korakot's library [241 articles]

Self-assembling hypertexts, weblogs, and wikis

Stuart Moulthrop — 2005-01-13T06:50:34-00:00

(2002), pp. 149-149.

Although most theory and research in the hypertext community has been directed toward systems and implementations with fairly conventional patterns of authorship, hypertext as it has evolved on the Internet contains a number of stranger species: Web logs (or "blogs") that consist largely of citations or pointers to other Web content; reader-writeable text spaces sometimes called "Wikis"; and in spaces outside the Web, shared writing environments like MUDs and MOOs. This panel brings together several writer/designers who have experience in one or more of these areas. The panelists will consider how open-form and self-assembling texts fit and stretch the hypertext paradigm, and what contribution these writing practices might make to the future of writing on the Net.

Detecting a network failure

J Kleinberg — 2005-12-05T05:32:37-00:00

(2000)

Maximizing the spread of influence through a social network

D Kempe — 2005-11-30T22:28:27-00:00

(2003)

Models for the processes by which ideas and influence propagate through a social network have been studied in a number of domains, including the diffusion of medical and technological innovations, the sudden and widespread adoption of various strategies in game-theoretic settings, and the effects of "word of mouth" in the promotion of new products. Recently, motivated by the design of viral marketing strategies, Domingos and Richardson posed a fundamental algorithmic problem for such social...

Zipf Law for Brazilian Cities

Newton Moura — 2005-11-29T23:52:07-00:00

(25 Nov 2005)

This work studies the Zipf Law for cities in Brazil. Data from censuses of 1970, 1980, 1991 and 2000 were used to select a sample containing only cities with 30,000 inhabitants or more. The results show that the population distribution in Brazilian cities does follow a power law similar to the ones found in other countries. Estimates of the power law exponent were found to be 2.22 +/- 0.34 for the 1970 and 1980 censuses, and 2.26 +/- 0.11 for censuses of 1991 and 2000. More accurate results were obtained with the maximum likelihood estimator, showing an exponent equal to 2.41 for 1970 and 2.36 for the other three years.

The Social Life of Information

John Brown — 2005-05-20T09:45:23-00:00

(15 February 2002)

Coevolution of dynamical states and interactions in dynamic networks

Martin Zimmermann — 2004-11-22T00:17:30-00:00

(17 May 2004)

We explore the coupled dynamics of the internal states of a set of interacting elements and the network of interactions among them. Interactions are modeled by a spatial game and the network of interaction links evolves adapting to the outcome of the game. As an example we consider a model of cooperation, where the adaptation is shown to facilitate the formation of a hierarchical interaction network that sustains a highly cooperative stationary state. The resulting network has the characteristics of a small world network when a mechanism of local neighbor selection is introduced in the adaptive network dynamics. The highly connected nodes in the hierarchical structure of the network play a leading role in the stability of the network. Perturbations acting on the state of these special nodes trigger global avalanches leading to complete network reorganization.

Search in weighted complex networks

Hari Thadakamalla — 2005-11-21T21:45:45-00:00

(18 Nov 2005)

We study complex trade-offs presented by local search algorithms in complex networks which are heterogeneous in edge weights and node degree. We show that search based on a novel network measure, local betweenness centrality (LBC), utilizes the heterogeneity of both node degrees and edge weights to perform the best in power-law weighted networks. The search based on LBC is universal and performs well in a large class of complex networks.

Finding and evaluating community structure in networks

MEJ Newman — 2004-11-22T00:17:30-00:00

(11 August 2003)

We propose and study a set of algorithms for discovering community structure in networks -- natural divisions of network nodes into densely connected subgroups. Our algorithms all share two definitive features: first, they involve iterative removal of edges from the network to split it into communities, the edges removed being identified using one of a number of possible "betweenness" measures, and second, these measures are, crucially, recalculated after each removal. We also propose a measure for the strength of the community structure found by our algorithms, which gives us an objective metric for choosing the number of communities into which a network should be divided. We demonstrate that our algorithms are highly effective at discovering community structure in both computer-generated and real-world network data, and show how they can be used to shed light on the sometimes dauntingly complex structure of networked systems.

Defining and identifying communities in networks

Filippo Radicchi — 2005-10-05T08:28:18-00:00

(27 Feb 2004)

The investigation of community structures in networks is an important issue in many domains and disciplines. This problem is relevant for social tasks (objective analysis of relationships on the web), biological inquiries (functional studies in metabolic, cellular or protein networks) or technological problems (optimization of large infrastructures). Several types of algorithm exist for revealing the community structure in networks, but a general and quantitative definition of community is still lacking, leading to an intrinsic difficulty in the interpretation of the results of the algorithms without any additional non-topological information. In this paper we face this problem by introducing two quantitative definitions of community and by showing how they are implemented in practice in the existing algorithms. In this way the algorithms for the identification of the community structure become fully self-contained. Furthermore, we propose a new local algorithm to detect communities which outperforms the existing algorithms with respect to the computational cost, keeping the same level of reliability. The new algorithm is tested on artificial and real-world graphs. In particular we show the application of the new algorithm to a network of scientific collaborations, which, for its size, can not be attacked with the usual methods. This new class of local algorithms could open the way to applications to large-scale technological and biological applications.

The centrality of groups and classes.

MG Everett — 2005-11-14T23:57:45-00:00

Journal of Mathematical Sociology, Vol. 23, No. 3. (1999), pp. 181-201.

Nonequilibrium transition induced by mass media in a model for social influence

JC González-Avella — 2005-11-09T07:16:02-00:00

(8 Nov 2005)

We study the effect of mass media, modeled as an applied external field, on a social system based on Axelrod's model for the dissemination of culture. The numerical simulations show that the system undergoes a nonequilibrium phase transition between an ordered phase (homogeneous culture) specified by the mass media and a disordered (culturally fragmented) one. The critical boundary separating these phases is calculated on the parameter space of the system, given by the intensity of the mass media influence and the number of options per cultural attribute. Counterintuitively, mass media can induce cultural diversity when its intensity is above some threshold value. The nature of the phase transition changes from continuous to discontinuous at some critical value of the number of options.

Don't take my folders away!: organizing personal information to get ghings done

William Jones — 2005-08-19T19:33:17-00:00

(2005), pp. 1505-1508.

We the Media

Dan Gillmor — 2005-07-16T11:56:35-00:00

(03 August 2004)

Grassroots journalists are dismantling Big Media's monopoly on the news, transforming it from a lecture to a conversation. Not content to accept the news as reported, these readers-turned-reporters are publishing in real time to a worldwide audience via the Internet. The impact of their work is just beginning to be felt by professional journalists and the newsmakers they cover. In We the Media: Grassroots Journalism by the People, for the People, nationally known business and technology columnist Dan Gillmor tells the story of this emerging phenomenon, and sheds light on this deep shift in how we make and consume the news.We the Media is essential reading for all participants in the news cycle:<ul> <li>Consumers learn how they can become producers of the news. Gillmor lays out the tools of the grassroots journalist's trade, including personal Web journals (called weblogs or blogs), Internet chat groups, email, and cell phones. He also illustrates how, in this age of media consolidation and diminished reporting, to roll your own news, drawing from the array of sources available online and even over the phone.</li> <li>Newsmakers politicians, business executives, celebrities get a wake-up call. The control that newsmakers enjoyed in the top-down world of Big Media is seriously undermined in the Internet Age. Gillmor shows newsmakers how to successfully play by the new rules and shift from control to engagement.</li> <li>Journalists discover that the new grassroots journalism presents opportunity as well as challenge to their profession. One of the first mainstream journalists to have a blog, Gillmor says, "My readers know more than I do, and that's a good thing." In We the Media, he makes the case to his colleagues that, in the face of a plethora of Internet-fueled news vehicles, they must change or become irrelevant.</li></ul> At its core, We the Media is a book about people. People like Glenn Reynolds, a law professor whose blog postings on the intersection of technology and liberty garnered him enough readers and influence that he became a source for professional journalists. Or Ben Chandler, whose upset Congressional victory was fueled by contributions that came in response to ads on a handful of political blogs. Or Iraqi blogger Zayed, whose Healing Irag blog (healingiraq.blogspot.com) scooped Big Media. Or acridrabbit, who inspired an online community to become investigative reporters and discover that the dying Kaycee Nichols sad tale was a hoax. Give the people tools to make the news, We the Media asserts, and they will. Journalism in the 21st century will be fundamentally different from the Big Media that prevails today. We the Media casts light on the future of journalism, and invites us all to be part of it.

Hubs, authorities, and communities

Jon Kleinberg — 2005-11-04T17:50:48-00:00

ACM Comput. Surv., Vol. 31, No. 4es. (1999)

The origin of bursts and heavy tails in human dynamics

Albert-László Barabási — 2005-11-02T15:00:45-00:00

(16 May 2005)

The dynamics of many social, technological and economic phenomena are driven by individual human actions, turning the quantitative understanding of human behavior into a central question of modern science. Current models of human dynamics, used from risk assessment to communications, assume that human actions are randomly distributed in time and thus well approximated by Poisson processes. In contrast, there is increasing evidence that the timing of many human activities, ranging from communication to entertainment and work patterns, follow non-Poisson statistics, characterized by bursts of rapidly occurring events separated by long periods of inactivity. Here we show that the bursty nature of human behavior is a consequence of a decision based queuing process: when individuals execute tasks based on some perceived priority, the timing of the tasks will be heavy tailed, most tasks being rapidly executed, while a few experience very long waiting times. In contrast, priority blind execution is well approximated by uniform interevent statistics. These findings have important implications from resource management to service allocation in both communications and retail.

Combining collaborative and contentbased filtering using conceptual graphs

P Paulson — 2005-10-30T17:41:48-00:00

(2003)

Collaborative Filtering and Content-Based Filtering are techniques used in the design of Recommender Systems that support personalization. Information that is available about the user, along with information about the collection of users on the system, can be processed in a number of ways in order to extract useful recommendations. There have been several algorithms developed, some of which we briefly introduce, which attempt to improve performance by maximizing the accuracy of their...

Social networks applied

S Staab — 2005-10-27T22:43:16-00:00

Intelligent Systems, IEEE [see also IEEE Intelligent Systems and Their Applications], Vol. 20, No. 1. (2005), pp. 80-93.

Social networks have interesting properties. They influence our lives enormously without us being aware of the implications they raise. The authors investigate the following areas concerning social networks: how to exploit our unprecedented wealth of data and how we can mine social networks for purposes such as marketing campaigns; social networks as a particular form of influence, i.e.., the way that people agree on terminology and this phenomenon's implications for the way we build ontologies and the Semantic Web; social networks as something we can discover from data; the use of social network information to offer a wealth of new applications such as better recommendations for restaurants, trustworthy email senders, or (maybe) blind dates; investigation of the richness and difficulty of harvesting FOAF (friend-of-a-friend) information; and by looking at how information processing is bound to social context, the resulting ways that network topology's definition determines its outcomes.

Sharp Transition towards Shared Vocabularies in Multi-Agent Systems

A Baronchelli — 2005-10-26T09:44:21-00:00

(9 Sep 2005)

What processes can explain how very large populations are able to converge on the use of a particular word or grammatical construction without global coordination? Answering this question helps to understand why new language constructs usually propagate along an S-shaped curve with a rather sudden transition towards global agreement. It also helps to analyze and design new technologies that support or orchestrate self-organizing communication systems, such as recent social tagging systems for the web. The article introduces and studies a microscopic model of communicating autonomous agents performing language games without any central control. We show that the system undergoes a disorder/order transition, going trough a sharp symmetry breaking process to reach a shared set of conventions. Before the transition, the system builds up non-trivial scale-invariant correlations, for instance in the distribution of competing synonyms, which display a Zipf-like law. These correlations make the system ready for the transition towards shared conventions, which, observed on the time-scale of collective behaviors, becomes sharper and sharper with system size. This surprising result not only explains why human language can scale up to very large populations but also suggests ways to optimize artificial semiotic dynamics.

Authoritative sources in a hyperlinked environment

Jon Kleinberg — 2004-11-22T00:17:30-00:00

Journal of the ACM, Vol. 46, No. 5. (1999), pp. 604-632.

The network structure of a hyperlinked environment can be a rich source of information about the content of the environment, provided we have effective means for understanding it. We develop a set of algorithmic tools for extracting information from the link structures of such environments, and report on experiments that demonstrate their effectiveness in a variety of context on the World Wide Web. The central issue we address within our framework is the distillation of broad search topics, through the discovery of “authorative” information sources on such topics. We propose and test an algorithmic formulation of the notion of authority, based on the relationship between a set of relevant authoritative pages and the set of “hub pages” that join them together in the link structure. Our formulation has connections to the eigenvectors of certain matrices associated with the link graph; these connections in turn motivate additional heuristrics for link-based analysis.

Small worlds: The structure of social networks

M Newman — 2005-10-25T13:51:54-00:00

Experimentally it has been found that any two people in the world, chosen at random, are connected to one another by a short chain of intermediate acquaintances, of typical length about six. This phenomenon, colloquially referred to as the six degrees of separation, has been the subject of a considerable amount of recent research and modeling, which we review here.

Vertex similarity in networks

EA Leicht — 2005-10-25T13:59:11-00:00

(14 Oct 2005)

We consider methods for quantifying the similarity of vertices in networks. We propose a measure of similarity based on the concept that two vertices are similar if their immediate neighbors in the network are themselves similar. This leads to a self-consistent matrix formulation of similarity that can be evaluated iteratively using only a knowledge of the adjacency matrix of the network. We test our similarity measure on computer-generated networks for which the expected results are known, and on a number of real-world networks.

Epidemics and percolation in small-world networks

Cristopher Moore — 2005-10-25T08:30:24-00:00

(7 Jan 2000)

We study some simple models of disease transmission on small-world networks, in which either the probability of infection by a disease or the probability of its transmission is varied, or both. The resulting models display epidemic behavior when the infection or transmission probability rises above the threshold for site or bond percolation on the network, and we give exact solutions for the position of this threshold in a variety of cases. We confirm our analytic results by numerical simulation.

Evolving networks by merging cliques

Kazuhiro Takemoto — 2005-10-20T00:24:43-00:00

(18 Oct 2005)

We propose a model for evolving networks by merging building blocks represented as complete graphs, reminiscent of modules in biological system or communities in sociology. The model shows power-law degree distributions, power-law clustering spectra and high average clustering coefficients independent of network size. The analytical solutions indicate that a degree exponent is determined by the ratio of the number of merging nodes to that of all nodes in the blocks, demonstrating that the exponent is tunable, and are also applicable when the blocks are classical networks such as Erd\Hos-Rényi or regular graphs. Our model becomes the same model as the Barabási-Albert model under a specific condition.

Solution for the properties of a clustered network

Juyong Park — 2005-10-20T00:26:30-00:00

(18 Oct 2005)

We study Strauss's model of a network with clustering and present an analytic mean-field solution which is exact in the limit of large network size. Previous computer simulations have revealed a degenerate region in the model's parameter space in which triangles of adjacent edges clump together to form unrealistically dense subgraphs, and perturbation calculations have been found to break down in this region at all orders. Our analytic solution shows that this region corresponds to a classic symmetry-broken phase and that the onset of the degeneracy corresponds to a first-order phase transition in the density of the network.

Towards a Theory of Scale-Free Graphs: Definition, Properties, and Implications (Extended Version)

Lun Li — 2005-10-19T18:43:40-00:00

(18 Oct 2005)

Although the “scale-free” literature is large and growing, it gives neither a precise definition of scale-free graphs nor rigorous proofs of many of their claimed properties. In fact, it is easily shown that the existing theory has many inherent contradictions and verifiably false claims. In this paper, we propose a new, mathematically precise, and structural definition of the extent to which a graph is scale-free, and prove a series of results that recover many of the claimed properties while suggesting the potential for a rich and interesting theory. With this definition, scale-free (or its opposite, scale-rich) is closely related to other structural graph properties such as various notions of self-similarity (or respectively, self-dissimilarity). Scale-free graphs are also shown to be the likely outcome of random construction processes, consistent with the heuristic definitions implicit in existing random graph approaches. Our approach clarifies much of the confusion surrounding the sensational qualitative claims in the scale-free literature, and offers rigorous and quantitative alternatives.

The structure of scientific collaboration networks

MEJ Newman — 2005-10-18T21:07:06-00:00

(12 Jul 2000)

We investigate the structure of scientific collaboration networks. We consider two scientists to be connected if they have authored a paper together, and construct explicit networks of such connections using data drawn from a number of databases, including MEDLINE (biomedical research), the Los Alamos e-Print Archive (physics), and NCSTRL (computer science). We show that these collaboration networks form "small worlds" in which randomly chosen pairs of scientists are typically separated by only a short path of intermediate acquaintances. We further give results for mean and distribution of numbers of collaborators of authors, demonstrate the presence of clustering in the networks, and highlight a number of apparent differences in the patterns of collaboration between the fields studied.

Small-world phenomena and the dynamics of information

J Kleinberg — 2005-10-14T11:59:50-00:00

(2001)

Introduction The problem of searching for information in networks like the World Wide Web can be approached in a variety of ways, ranging from centralized indexing schemes to decentralized mechanisms that navigate the underlying network without knowledge of its global structure. The decentralized approach appears in a variety of settings: in the behavior of users browsing the Web by following hyperlinks; in the design of focused crawlers [4, 5, 8] and other agents that explore the Web's links...

Deterministic Scale-Free Networks

Albert-Laszlo Barabasi — 2005-09-27T10:09:48-00:00

(6 Feb 2002)

Scale-free networks are abundant in nature and society, describing such diverse systems as the world wide web, the web of human sexual contacts, or the chemical network of a cell. All models used to generate a scale-free topology are stochastic, that is they create networks in which the nodes appear to be randomly connected to each other. Here we propose a simple model that generates scale-free networks in a deterministic fashion. We solve exactly the model, showing that the tail of the degree distribution follows a power law.

Shortest paths and load scaling in scale-free trees.

B Bollobás — 2004-11-22T00:17:30-00:00

Phys Rev E Stat Nonlin Soft Matter Phys, Vol. 69, No. 3 Pt 2. (March 2004)

Szabó, Alava, and Kertész [Phys. Rev. E 66, 026101 (2002)] considered two questions about the scale-free random tree given by the m=1 case of the Barabási-Albert (BA) model (identical with a random tree model introduced by Szymański in 1987): what is the distribution of the node to node distances, and what is the distribution of node loads, where the load on a node is the number of shortest paths passing through it? They gave heuristic answers to these questions using a "mean-field" approximation, replacing the random tree by a certain fixed tree with carefully chosen branching ratios. By making use of our earlier results on scale-free random graphs, we shall analyze the random tree rigorously, obtaining and proving very precise answers to these questions. We shall show that, after dividing by N (the number of nodes), the load distribution converges to an integer distribution X with Pr(X=c)=2/[(2c+1)(2c+3)], c=0,1,2,..., confirming the asymptotic power law with exponent -2 predicted by Szabó, Alava, and Kertész. For the distribution of node-node distances, we show asymptotic normality, and give a precise form for the (far from normal) large deviation law. We note that the mean-field methods used by Szabó, Alava, and Kertész give very good results for this model.

Network Forms of Organization

Joel Podolny — 2005-03-26T19:05:18-00:00

Annual Review of Sociology, Vol. 24 (1998), pp. 57-76.

Initial sociological interest in network forms of organization was motivated in part by a critique of economic views of organization. Sociologists sought to highlight the prevalence and functionality of organizational forms that could not be classified as markets or hierarchies. As a result of this work, we now know that network forms of organization foster learning, represent a mechanism for the attainment of status or legitimacy, provide a variety of economic benefits, facilitate the management of resource dependencies, and provide considerable autonomy for employees. However, as sociologists move away from critiquing what are now somewhat outdated economic views, they need to balance the exclusive focus on prevalence and functionality with attention to constraint and dysfunctionality. The authors review work that has laid a foundation for this broader focus and suggest analytical concerns that should guide this literature as it moves forward.

An Experimental Study of the Small World Problem

Jeffrey Travers — 2005-09-02T20:33:54-00:00

Sociometry, Vol. 32, No. 4. (1969), pp. 425-443.

Arbitrarily selected individuals (N = 296) in Nebraska and Boston are asked to generate acquaintance chains to a target person in Massachusetts, employing "the small world method" (Milgram, 1967). Sixty-four chains reach the target person. Within this group the mean number of intermediaries between starters and targets is 5.2. Boston starting chains reach the target person with fewer intermediaries than those starting in Nebraska; subpopulations in the Nebraska group do not differ among themselves. The funneling of chains through sociometric ßtars" is noted, with 48 per cent of the chains passing through three persons before reaching the target. Applications of the method to studies of large scale social structure are discussed.

The structure of broad topics on the Web

S Chakrabarti — 2005-10-11T17:48:09-00:00

(2002)

The Web graph is a giant social network whose properties have been measured and modeled extensively in recent years. Most such studies concentrate on the graph structure alone, and do not consider textual properties of the nodes. Consequently, Web communities have been characterized purely in terms of graph structure and not on page content. We propose that a topic taxonomy such as Yahoo! or the Open Directory provides a useful framework for understanding the structure of content-based clusters ...

Instability of defensive alliances in the predator-prey model on complex networks

Beom Kim — 2005-10-10T21:50:09-00:00

(7 Oct 2005)

A model of six-species food web is studied in the viewpoint of spatial interaction structures. Each species has two predators and two preys, and it was previously known that the defensive alliances of three cyclically predating species self-organize in two-dimensions. The alliance-breaking transition occurs as either the mutation rate is increased or interaction topology is randomized in the scheme of the Watts-Strogatz model. In the former case of temporal disorder, via the finite-size scaling analysis the transition is clearly shown to belong to the two-dimensional Ising universality class. In contrast, the geometric or spatial randomness for the latter case yields a discontinuous phase transition. The mean-field limit of the model is analytically solved and then compared with numerical results. The dynamic universality and the temporally periodic behaviors are also discussed.

The power of collective intelligence

Aaron Weiss — 2005-10-10T03:30:29-00:00

netWorker, Vol. 9, No. 3. (September 2005), pp. 16-23.

Folksonomy as a Complex Network

Kaikai Shen — 2005-10-22T10:31:18-00:00

(23 Sep 2005)

Folksonomy is an emerging technology that works to classify the information over WWW through tagging the bookmarks, photos or other web-based contents. It is understood to be organized by every user while not limited to the authors of the contents and the professional editors. This study surveyed the folksonomy as a complex network. The result indicates that the network, which is composed of the tags from the folksonomy, displays both properties of small world and scale-free. However, the statistics only shows a local and static slice of the vast body of folksonomy which is still evolving.

Renormalizing Sznajd model on complex networks taking into account the effects of growth mechanisms

MC Gonzalez — 2005-10-07T04:35:35-00:00

(5 Oct 2005)

We present a renormalization approach to solve the Sznajd opinion formation model on complex networks. For the case of two opinions, we present an expression of the probability of reaching consensus for a given opinion as a function of the initial fraction of agents with that opinion. The calculations reproduce the sharp transition of the model on a fixed network, as well as the recently observed smooth function for the model when simulated on a growing complex networks.

A common origin of the power law distributions in models of market and earthquake

Pratip Bhattacharyya — 2005-10-07T04:36:15-00:00

(5 Oct 2005)

We show here that the Pareto power law distribution observed in an ideal gas-like trading market model (with random saving propensity of its agents) and the Gutenberg-Richter like distribution for the overlap measure between two Cantor sets (as one moves uniformly over the other in a dynamical model of earthquakes) have a common origin. The identification of this common generic origin helps in developing generalized views and understanding of such diverse phenomena.

Personal knowledge publishing: fostering interdisciplinary communication

E Aimeur — 2005-10-06T18:49:23-00:00

Intelligent Systems, IEEE [see also IEEE Intelligent Systems and Their Applications], Vol. 20, No. 2. (2005), pp. 46-53.

We address this article in relation to blogging and personal knowledge publishing (PKP). Derived from blogging, personal knowledge publishing is a form of Web-based communication that lowers social and linguistic barriers, facilitating knowledge migration across disciplinary boundaries. The aggregate output of this practice could provide a promising basis for intelligent systems development. These individual-centered, community-discussion-support systems have emerged as an interesting complement to journals, mailing lists, and other media for interdisciplinary-minded individuals. PKP offers individual researchers a tool for building strong interdisciplinary research networks. These networks enable individuals to find relevant literature and experts outside their core research community.

Who is the best connected scientist? A study of scientific coauthorship networks

MEJ Newman — 2005-10-05T08:15:07-00:00

(28 Nov 2000)

Using data from computer databases of scientific papers in physics, biomedical research, and computer science, we have constructed networks of collaboration between scientists in each of these disciplines. In these networks two scientists are considered connected if they have coauthored one or more papers together. We have studied many statistical properties of our networks, including numbers of papers written by authors, numbers of authors per paper, numbers of collaborators that scientists have, typical distance through the network from one scientist to another, and a variety of measures of connectedness within a network, such as closeness and betweenness. We further argue that simple networks such as these cannot capture the variation in the strength of collaborative ties and propose a measure of this strength based on the number of papers coauthored by pairs of scientists, and the number of other scientists with whom they coauthored those papers. Using a selection of our results, we suggest a variety of possible ways to answer the question "Who is the best connected scientist?"

Quantitive and sociological analysis of blog networks

Wiktor Bachnik — 2005-10-04T17:29:19-00:00

(7 Jun 2005)

This paper examines the emerging phenomenon of blogging, using three different Polish blogging services as the base of the research. Authors show that blog networks are sharing their characteristics with complex networks gamma coefficients, small worlds, cliques, etc.). Elements of sociometric analysis were used to prove existence of some social structures in the blog networks.

Incentives Build Robustness in BitTorrent

Bram Cohen — 2004-12-20T08:32:02-00:00

(2003)

The BitTorrent file distribution system uses tit-for-tat as a method of seeking pareto efficiency. It achieves a higher level of robustness and resource utilization than any currently known cooperative technique. We explain what BitTorrent does, and how economic methods are used to achieve that goal.

Scale-free topology of e-mail networks

Holger Ebel — 2005-09-30T09:21:19-00:00

(12 Feb 2002)

We study the topology of e-mail networks with e-mail addresses as nodes and e-mails as links using data from server log files. The resulting network exhibits a scale-free link distribution and pronounced small-world behavior, as observed in other social networks. These observations imply that the spreading of e-mail viruses is greatly facilitated in real e-mail networks compared to random architectures.

Authoritative sources in a hyperlinked environment

Jon Kleinberg — 2005-09-30T23:34:58-00:00

Journal of the ACM, Vol. 46, No. 5. (1999), pp. 604-632.

The link structure of a hypermedia environment can be a rich source of information about the content of the environment, provided we have effective means for understanding it. Versions of this principle have been studied in the hypertext research community and (in a context predating hypermedia) through journal citation analysis in the field of bibliometrics. But for the problem of searching in hyperlinked environments such as the World Wide Web, it is clear from the prevalent techniques that...

Assortative mixing in networks

MEJ Newman — 2005-09-30T09:19:51-00:00

(20 May 2002)

A network is said to show assortative mixing if the nodes in the network that have many connections tend to be connected to other nodes with many connections. We define a measure of assortative mixing for networks and use it to show that social networks are often assortatively mixed, but that technological and biological networks tend to be disassortative. We propose a model of an assortative network, which we study both analytically and numerically. Within the framework of this model we find that assortative networks tend to percolate more easily than their disassortative counterparts and that they are also more robust to vertex removal.

Why social networks are different from other types of networks

MEJ Newman — 2005-09-30T09:20:29-00:00

(26 May 2003)

We argue that social networks differ from most other types of networks, including technological and biological networks, in two important ways. First, they have non-trivial clustering or network transitivity, and second, they show positive correlations, also called assortative mixing, between the degrees of adjacent vertices. Social networks are often divided into groups or communities, and it has recently been suggested that this division could account for the observed clustering. We demonstrate that group structure in networks can also account for degree correlations. We show using a simple model that we should expect assortative mixing in such networks whenever there is variation in the sizes of the groups and that the predicted level of assortative mixing compares well with that observed in real-world networks.

Fifteen Minutes of Fame: The Dynamics of Information Access on the Web

Z Dezso — 2005-06-08T10:36:29-00:00

(12 May 2005)

While current studies on complex networks focus on systems that change relatively slowly in time, the structure of the most visited regions of the Web is altered at the timescale from hours to days. Here we investigate the dynamics of visitation of a major news portal, representing the prototype for such a rapidly evolving network. The nodes of the network can be classified into stable nodes, that form the time independent skeleton of the portal, and news documents. The visitation of the two node classes are markedly different, the skeleton acquiring visits at a constant rate, while a news document's visitation peaking after a few hours. We find that the visitation pattern of a news document decays as a power law, in contrast with the exponential prediction provided by simple models of site visitation. This is rooted in the inhomogeneous nature of the browsing pattern characterizing individual users: the time interval between consecutive visits by the same user to the site follows a power law distribution, in contrast with the exponential expected for Poisson processes. We show that the exponent characterizing the individual user's browsing patterns determines the power-law decay in a document's visitation. Finally, our results document the fleeting quality of news and events: while fifteen minutes of fame is still an exaggeration in the online media, we find that access to most news items significantly decays after 36 hours of posting.

Statistics of citation networks

Alexei Vazquez — 2005-09-29T10:50:56-00:00

(2 May 2001)

The out-degree distribution of citation networks is investigated. Statistical data of the number of papers cited within a paper (out-degree) for different journals in the period 1991-1999 is reported. The out-degree distribution is characterized by a maximum at intermediate out-degrees. At the left of the maximum there are strong fluctuations from journal to journal while is quite universal at the right, with two classes of journals. These two classes are associated with the existence or not of a restriction in the maximum number of pages per paper. The shape of the out-degree distribution does not change appreciable from period to period, but the average out-degree is observed to increase logarithmically with the number of published papers. These features are modeled using a recursive search model.

Norm formation in social influence networks

Noah Friedkin — 2005-09-27T22:01:05-00:00

Social Networks, Vol. 23, No. 3. (July 2001), pp. 167-189.

I propose a mechanism of norm formation and maintenance that combines classical theory in social psychology on attitudes and social comparisons with a formal network theory of social influence. Underlying the formation of norms is the ubiquitous belief that there is a correct response for every situation and an abiding interest for persons to base their responses on these correct foundations. Given such a belief, a normative evaluation of a feeling, thought or action is likely to arise when persons perceive that their positive or negative attitudinal evaluation is shared by one or more influential others. If interpersonal agreements validate attitudes and transform attitudes into norms, then the development of a theory of norm formation may draw on extant "combinatorial" theories of consensus production that describe how shared attitudes are produced and maintained in groups. The network theory of social influence that I employ is one such combinatorial approach. An important sociological implication of this network theory is that the content of norms must be consistent with the social stratification (or more general pattern of inequality) of interpersonal influences in a group. I illustrate the theory with an analysis of Roethlisberger and Dickson’s (1939) classic observations on the Bank Wiring Observation Room.

Evolution of networks

SN Dorogovtsev — 2005-09-27T15:02:02-00:00

(7 Sep 2001)

We review the recent fast progress in statistical physics of evolving networks. Interest has focused mainly on the structural properties of random complex networks in communications, biology, social sciences and economics. A number of giant artificial networks of such a kind came into existence recently. This opens a wide field for the study of their topology, evolution, and complex processes occurring in them. Such networks possess a rich set of scaling properties. A number of them are scale-free and show striking resilience against random breakdowns. In spite of large sizes of these networks, the distances between most their vertices are short -- a feature known as the “small-world” effect. We discuss how growing networks self-organize into scale-free structures and the role of the mechanism of preferential linking. We consider the topological and structural properties of evolving networks, and percolation in these networks. We present a number of models demonstrating the main features of evolving networks and discuss current approaches for their simulation and analytical study. Applications of the general results to particular networks in Nature are discussed. We demonstrate the generic connections of the network growth processes with the general problems of non-equilibrium physics, econophysics, evolutionary biology, etc.

The Network Paradigm in Organizational Research: A Review and Typology

Stephen Borgatti — 2005-09-26T22:13:51-00:00

Journal of Management, Vol. 29, No. 6. (December 2003), pp. 991-1013.

In this paper, we review and analyze the emerging network paradigm in organizational research. We begin with a conventional review of recent research organized around recognized research streams. Next, we analyze this research, developing a set of dimensions along which network studies vary, including direction of causality, levels of analysis, explanatory goals, and explanatory mechanisms. We use the latter two dimensions to construct a 2-by-2 table cross-classifying studies of network consequences into four canonical types: structural social capital, social access to resources, contagion, and environmental shaping. We note the rise in popularity of studies with a greater sense of agency than was traditional in network research.