| |
(9 Mar 2010)
Abstract
The past few years have witnessed the great success of a new family of paradigms, so-called folksonomy, which allows users to freely associate tags to resources and efficiently manage them. In order to uncover the underlying structures and user behaviors in folksonomy, in this paper, we propose an evolutionary hypergrah model to explain the emerging statistical properties. The present model introduces a novel mechanism that one can not only assign tags to resources, but also retrieve resources via collaborative tags. We then compare the model with a real-world ...
|
| |
In CNIKM '09: Proceeding of the 1st ACM international workshop on Complex networks meet information \&\#38; knowledge management (2009), pp. 31-38.
Abstract
Measuring the centrality of nodes in real-world networks has remained an important task in the technological, social, and biological network paradigms carrying implications on their analysis and applications. Exact inference of centrality values is infeasible in large networks due to the need to solve the all-pairs shortest path problem. We introduce a framework to approximate node centralities in real-world networks that are known to exhibit modularity, i.e., the presence of dense subgraphs or communities, which are themselves sparsely connected. We also ...
|
| |
Physical Review E, Vol. 79, No. 6. (Jun 2009), 066107.
Abstract
The recent boom of large-scale online social networks (OSNs) both enables and necessitates the use of parallelizable and scalable computational techniques for their analysis. We examine the problem of real-time community detection and a recently proposed linear time— O ( m ) on a network with m edges—label propagation, or “epidemic” community detection algorithm. We identify characteristics and drawbacks of the algorithm and extend it by incorporating different heuristics to facilitate reliable and multifunctional real-time community detection. With ...
|
| |
Physical Review E, Vol. 80, No. 2. (Aug 2009), 026129.
Abstract
We investigate the recently proposed label-propagation algorithm (LPA) for identifying network communities. We reformulate the LPA as an equivalent optimization problem, giving an objective function whose maxima correspond to community solutions. By considering properties of the objective function, we identify conceptual and practical drawbacks of the label-propagation approach, most importantly the disparity between increasing the value of the objective function and improving the quality of communities found. To address the drawbacks, we modify the objective function in the optimization problem, producing ...
|
| |
Physical Review Letters, Vol. 92, No. 17. (27 Apr 2004), 178701.
Abstract
We study the effect of the connectivity pattern of complex networks on the propagation dynamics of epidemics. The growth time scale of outbreaks is inversely proportional to the network degree fluctuations, signaling that epidemics spread almost instantaneously in networks with scale-free degree distributions. This feature is associated with an epidemic propagation that follows a precise hierarchical dynamics. Once the highly connected hubs are reached, the infection pervades the network in a progressive cascade across smaller degree classes. The present results are ...
|
| |
Genome Research, Vol. 14, No. 3. (March 2004), pp. 391-397.
Abstract
10.1101/gr.1969504 Functional modules are considered the primary building blocks of biomolecular systems. Here we study to what extent functional modules behave cohesively across genomes:That is, are functional modules also evolutionary modules? We probe this question by analyzing for a large collection of functional modules the phyletic patterns of their genes across 110 genomes. The majority of functional modules display limited evolutionary modularity. This result confirms certain comparative genome analyses, but is in contrast to implicit assumptions in the systems analysis of ...
|
| |
Physica A: Statistical Mechanics and its Applications, Vol. 387, No. 25. (01 November 2008), pp. 6436-6442.
Abstract
In this paper we study the reconstruction of a network topology from the eigenvalues of its Laplacian matrix. We introduce a simple cost function and consider the tabu search combinatorial optimization method, while comparing its performance when reconstructing different categories of networks–random, regular, small-world, scale-free and clustered–from their eigenvalues. We show that this combinatorial optimization method, together with the information contained in the Laplacian spectrum, allows an exact reconstruction of small networks and leads to good approximations in the case of ...
|
| |
(18 Jan 2010)
Abstract
Many models have been proposed to analyze the evolution of opinion structure due to the interaction of individuals in their social environment. Such models analyze the spreading of ideas both in completely interacting backgrounds and on social networks, where each person has a finite set of interlocutors.Moreover, the investigation on the topological structure of social networks has been the object of several analyses, both from the theoretical and the empirical point of view. In this framework a particularly important area of study involves the community structure inside social networks.In ...
|
| |
(24 Feb 2010)
Abstract
The use of dyadic interaction between agents, in combination with homophily (the principle that “likes attract”) in the Axelrod model for the study of cultural dissemination has two important problems: the prediction of monoculture in large societies and an extremely narrow window of noise levels in which diversity with local convergence is obtained. Recently, the inclusion of social influence has proven to overcome them (A. Flache and M. W. Macey, <a href="/abs/0808.2710">arXiv:0808.2710</a>). Here we extend the Axelrod model with social influence interaction for the study ...
|
| |
(24 Feb 2010)
Abstract
We apply the approach of the Google matrix, used in computer science and World Wide Web, to description of properties of neuronal networks. The Google matrix $ G$ is constructed on the basis of neuronal network of a brain model discussed in PNAS 105, 3593 (2008). We show that the spectrum of eigenvalues of $ G$ has a gapless structure with long living relaxation modes. The PageRank of the network becomes delocalized for certain values of the Google damping factor $α$. The properties of other eigenstates ...
|
| |
(24 Feb 2010)
Abstract
We study the large time fluctuations of entropy production in Markov processes. In particular, we consider the effect of a coarse-graining procedure which decimates fast states with respect to a given time threshold. Our results provide strong evidence that entropy production is not directly affected by this decimation, provided that it does not entirely remove loops carrying a net probability current. After the study of some examples of random walks on simple graphs, we apply our analysis to a network model for the kinesin cycle, which is ...
|
| |
(24 Feb 2010)
Abstract
A method based on multicanonical Monte Carlo is applied to the calculation of large deviations in the largest eigenvalue of random matrices. The method is successfully tested with the Gaussian orthogonal ensemble (GOE), sparse random matrices, and matrices whose components are subject to uniform density. Specifically, the probability that all eigenvalues of a matrix are negative is estimated in these cases down to the values of $∼ 10^-200$, a region where naive random sampling is ineffective. The method can be applied to any ensemble of matrices and used ...
|
| |
In HT '09: Proceedings of the 20th ACM conference on Hypertext and hypermedia (2009), pp. 245-250.
Abstract
Real-world relations are often represented as bipartite networks, such as paper-author networks and event-attendee networks. Extracting dense subnetworks (communities) from bipartite networks and evaluating their qualities are practically important research topics. As the attempts for evaluating divisions of bipartite networks, Guimera and Barber propose bipartite modularities. This paper discusses the properties of these bipartite modularities and proposes another bipartite modularity that allows one-to-many correspondence of communities of different vertex types. Preliminary experimental results for the bipartite modularities are also described. ...
|
| |
Intelligence and Security Informatics In Intelligence and Security Informatics , Vol. 3975 (2006), pp. 154-165.
Abstract
Since privacy information can be inferred via social relations, the privacy confidentiality problem becomes increasingly challenging as online social network services are more popular. Using a Bayesian network approach to model the causal relations among people in social networks, we study the impact of prior probability, influence strength, and society openness to the inference accuracy on a real online social network. Our experimental results reveal that personal attributes can be inferred with high accuracy especially when people are connected with strong ...
|
| |
(12 Oct 2009)
Abstract
A modularity-specialized label propagation algorithm (LPAm) for detecting network communities was recently proposed. This promising algorithm offers some desirable qualities. However, LPAm favors community divisions where all communities are similar in total degree and thus it is prone to get stuck in poor local maxima in the modularity space. To escape local maxima, we employ a multistep greedy agglomerative algorithm (MSG) that can merge multiple pairs of communities at a time. Combining LPAm and MSG, we propose an advanced modularity-specialized label propagation algorithm (LPAm+). Experiments show that LPAm+ successfully ...
|
| |
(22 May 2009)
Abstract
We introduce an ambidextrous view of stochastic dynamical systems, comparing their forward-time and reverse-time representations and then integrating them into a single time-symmetric representation. The perspective is useful theoretically, computationally, and conceptually. Mathematically, we prove that the excess entropy--a familiar measure of organization in complex systems--is the mutual information not only between the past and future, but also between the predictive and retrodictive causal states. Practically, we exploit the connection between prediction and retrodiction to directly calculate the excess entropy. Conceptually, these lead one to discover new system invariants ...
|
| |
Artificial Intelligence, Vol. 72, No. 1-2. (January 1995), pp. 173-215.
Abstract
Using the language of dynamical systems theory, a general theoretical framework for the synthesis and analysis of autonomous agents is sketched. In this framework, an agent and its environment are modeled as two coupled dynamical systems whose mutual interaction is in general jointly responsible for the agent's behavior. In addition, the adaptive fit between an agent and its environment is characterized in terms of the satisfaction of a given constraint on the trajectories of the coupled agent-environment system. The utility of ...
|
| |
In ISMSE '04: Proceedings of the IEEE Sixth International Symposium on Multimedia Software Engineering (2004), pp. 337-343.
Abstract
The integration of life-log data in different media enables to represent the same activities from various viewpoints. Integrated life-log data represent contexts each other that are not able to represent in single. Each media has its own characteristic features, and the limitation on its content representation ability. Life-log data consists of records of activities. Examples of life-log data are the e-mail massages that he/she sent and received, TV programs that he/she watched, and photographs that he/she took, and so on. One ...
|
| |
(1 Oct 2009)
Abstract
Although widely used in practice, the behavior and accuracy of the popular module identification technique called modularity maximization is not well understood. Here, we present a broad and systematic characterization of its performance in practical situations. First, we generalize and clarify the recently identified resolution limit phenomenon. Second, we show that the modularity function Q exhibits extreme degeneracies: that is, the modularity landscape admits an exponential number of distinct high-scoring solutions and does not typically exhibit a clear global maximum. Third, we derive the limiting behavior of the maximum ...
|
| |
Trends in Ecology & Evolution In BUMPER BOOK REVIEW, Vol. 20, No. 6. (June 2005), pp. 345-353.
Abstract
Although pairwise interactions have always had a key role in ecology and evolutionary biology, the recent increase in the amount and availability of biological data has placed a new focus on the complex networks embedded in biological systems. The increased availability of computational tools to store and retrieve biological data has facilitated wide access to these data, not just by biologists but also by specialists from the social sciences, computer science, physics and mathematics. This fusion of interests has led to ...
|
| |
Physical Review E, Vol. 76, No. 2. (Aug 2007), 026109.
Abstract
We apply random matrix theory to complex networks. We show that nearest neighbor spacing distribution of the eigenvalues of the adjacency matrices of various model networks, namely scale-free, small-world, and random networks follow universal Gaussian orthogonal ensemble statistics of random matrix theory. Second, we show an analogy between the onset of small-world behavior, quantified by the structural properties of networks, and the transition from Poisson to Gaussian orthogonal ensemble statistics, quantified by Brody parameter characterizing a spectral property. We also present ...
|
| |
Physical Review E, Vol. 80, No. 6. (Dec 2009), 066119.
Abstract
In human societies, opinion formation is mediated by social interactions, consequently taking place on a network of relationships and at the same time influencing the structure of the network and its evolution. To investigate this coevolution of opinions and social interaction structure, we develop a dynamic agent-based network model by taking into account short range interactions like discussions between individuals, long range interactions like a sense for overall mood modulated by the attitudes of individuals, and external field corresponding to outside ...
|
| |
Physics Reports, Vol. 486, No. 3-5. (17 February 2010), pp. 75-174.
Abstract
The modern science of networks has brought significant advances to our understanding of complex systems. One of the most relevant features of graphs representing real systems is community structure, or clustering, i.e. the organization of vertices in clusters, with many edges joining vertices of the same cluster and comparatively few edges joining vertices of different clusters. Such clusters, or communities, can be considered as fairly independent compartments of a graph, playing a similar role like, e.g., the tissues or the organs ...
|
| |
Nature, Vol. 457, No. 7228. (03 December 2008), pp. 463-466.
Abstract
In theoretical ecology, simple stochastic models that satisfy two basic conditions about the distribution of niche values and feeding ranges have proved successful in reproducing the overall structural properties of real food webs, using species richness and connectance as the only input parameters1, 2, 3, 4. Recently, more detailed models have incorporated higher levels of constraint in order to reproduce the actual links observed in real food webs5, 6. Here, building on previous stochastic models of consumer–resource interactions between species1, 2, ...
|
| |
(10 Nov 2009)
Abstract
During the last decade, the science of networks has grown into an enormous interdisciplinary endeavor, with methods and applications drawn from across the natural, social, and information sciences. One of the most important and prominent ideas from network science is the algorithmic detection of tightly-connected groups of nodes known as communities. Here we develop a formulation to detect communities in a very broad setting by studying general dynamical processes on networks. We create a new framework of network quality functions that allows us to study the community structure ...
|
| |
Transactions of the Japanese Society for Artificial Intelligence, Vol. 25, No. 1. (2010), pp. 16-24.
Abstract
Community detection in networks receives much attention recently. Most of the previous works are for unipartite networks composed of only one type of nodes. In real world situations, however, there are many bipartite networks composed of two types of nodes. In this paper, we propose a fast algorithm called LP&BRIM for community detection in large-scale bipartite networks. It is based on a joint strategy of two developed algorithms -- label propagation (LP), a very fast community detection algorithm, and BRIM, an ...
|
| |
In IDIAP-RR 11, IDIAP (2006)
Abstract
Abstract. Spiking Neuron Networks (SNNs) are often referred to as the 3 rd generation of neural networks. They derive their strength and interest from an accurate modelling of synaptic interactions between neurons, taking into account the time of spike emission. SNNs overcome the computational power of neural networks made of threshold or sigmoidal units. Based on dynamic event-driven processing, they open up new horizons for developping models with an exponential capacity of memorizing and a strong ability to fast adaptation. Today, ...
|
| |
(22 Dec 2009)
Abstract
In this paper, we develop the idea to partition the edges of a graph in order to uncover overlapping communities of its nodes. Our approach is based on the construction of different types of weighted line graphs, i.e. graphs whose nodes are the links of the original graph, that encapsulate differently the relations between the edges. Weighted line graphs are argued to provide an alternative, valuable representation of the system's topology, and are shown to have important applications in community detection, as the usual node partition of a ...
|
| |
Physical Review E (Statistical, Nonlinear, and Soft Matter Physics), Vol. 75, No. 3. (2007), 036109.
Abstract
In this paper we study a simple cascading process in a structured heterogeneous population, namely, a network composed of two loosely coupled communities. We demonstrate that under certain conditions the cascading dynamics in such a network has a two-tiered structure that characterizes activity spreading at different rates in the communities. We study the dynamics of the model using both simulations and an analytical approach based on annealed approximation and obtain good agreement between the two. Our results suggest that network modularity ...
|
| |
The American Mathematical Monthly, Vol. 41, No. 7. (1934), pp. 411-419.
|
| |
Nature, Vol. 433, No. 7024. (27 January 2005), pp. 392-395.
Abstract
Complex networks have been studied extensively owing to their relevance to many real systems such as the world-wide web, the Internet, energy landscapes and biological and social networks1, 2, 3, 4, 5. A large number of real networks are referred to as 'scale-free' because they show a power-law distribution of the number of links per node1, 6, 7. However, it is widely believed that complex networks are not invariant or self-similar under a length-scale transformation. This conclusion originates from the 'small-world' ...
|
| |
Science (New York, N.Y.), Vol. 325, No. 5939. (24 July 2009), pp. 412-413.
Abstract
For decades, we tacitly assumed that the components of such complex systems as the cell, the society, or the Internet are randomly wired together. In the past decade, an avalanche of research has shown that many real networks, independent of their age, function, and scope, converge to similar architectures, a universality that allowed researchers from different disciplines to embrace network theory as a common paradigm. The decade-old discovery of scale-free networks was one of those events that had helped catalyze the ...
|
| |
Physical Review E (Statistical, Nonlinear, and Soft Matter Physics), Vol. 76, No. 4. (2007), 046115.
Abstract
One-mode projecting is extensively used to compress bipartite networks. Since one-mode projection is always less informative than the bipartite representation, a proper weighting method is required to better retain the original information. In this article, inspired by the network-based resource-allocation dynamics, we raise a weighting method which can be directly applied in extracting the hidden information of networks, with remarkably better performance than the widely used global ranking method as well as collaborative filtering. This work not only provides a creditable ...
|
| |
Proceedings of the National Academy of Sciences of the United States of America, Vol. 101, No. Suppl 1. (6 April 2004), pp. 5291-5296.
Abstract
10.1073/pnas.0307604100 A crossmapping technique is introduced for visualizing multiple and overlapping relations among entity types in collections of journal articles. Groups of entities from two entity types are crossplotted to show correspondence of relations. For example, author collaboration groups are plotted on the axis against groups of papers (research fronts) on the axis. At the intersection of each pair of author group/research front pairs a circular symbol is plotted whose size is proportional to the number of times that ...
|
| |
Social Networks, Vol. 30, No. 1. (January 2008), pp. 31-48.
Abstract
Many large real-world networks actually have a two-mode nature: their nodes may be separated into two classes, the links being between nodes of different classes only. Despite this, and despite the fact that many ad hoc tools have been designed for the study of special cases, very few exist to analyse (describe, extract relevant information) such networks in a systematic way. We propose here an extension of the most basic notions used nowadays to analyse large one-mode networks (the classical case) ...
|
| |
(8 Mar 2005)
Abstract
This work presents a model that allows the study of research specialties through the manifestations of the specialty's social and epistemological processes in a collection of journal papers. Collections of papers are modeled as coupled bipartite networks interlinking 7 types of entities. Matrix-based link weight functions are introduced to calculate weighted bipartite networks and weighted unipartite co-occurrence networks in the collection of papers. These weight calculation methods, when used in conjunction with unweighted bipartite growth models, produce simple growth models for weighted networks in collections of papers. ...
|
| |
Journal of Statistical Mechanics: Theory and Experiment, Vol. 2006, No. 01. (21 Nov 2005), P01010.
Abstract
Collaboration networks are studied as an example of growing bipartite networks. These have been previously observed to have structure such as positive correlations between nearest-neighbour degrees. However, a detailed understanding of the origin of this phenomenon and the growth dynamics is lacking. Both of these are analyzed empirically and simulated using various models. A new one is presented, incorporating empirically necessary ingredients such as bipartiteness and sublinear preferential attachment. This, and a recently proposed model of team assembly both agree roughly with some empirical observations and fail in several ...
|
| |
(5 Apr 2004)
Abstract
We consider a dynamic social network model in which agents play repeated games in pairings determined by a stochastically evolving social network. Individual agents begin to interact at random, with the interactions modeled as games. The game payoffs determine which interactions are reinforced, and the network structure emerges as a consequence of the dynamics of the agents' learning behavior. We study this in a variety of game-theoretic conditions and show that the behavior is complex and sometimes dissimilar to behavior in the absence of structural dynamics. We argue ...
|
| |
(29 Dec 2005)
Abstract
We describe online collaborative communities by tripartite networks, the nodes being persons, items and tags. We introduce projection methods in order to uncover the structures of the networks, i.e. communities of users, genre families... To do so, we focus on the correlations between the nodes, depending on their profiles, and use percolation techniques that consist in removing less correlated links and observing the shaping of disconnected islands. The structuring of the network is visualised by using a tree representation. The notion of diversity in the system is also discussed. ...
|
| |
(23 October 2002)
Abstract
Mining the Web: Discovering Knowledge from Hypertext Data is the first book devoted entirely to techniques for producing knowledge from the vast body of unstructured Web data. Building on an initial survey of infrastructural issuesincluding Web crawling and indexingChakrabarti examines low-level machine learning techniques as they relate specifically to the challenges of Web mining. He then devotes the final part of the book to applications that unite infrastructure and analysis to bring machine learning to bear on systematically acquired and stored ...
|
| |
(26 May 2003)
Abstract
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 ...
|
| |
Science, Vol. 298, No. 5594. (25 October 2002), pp. 824-827.
Abstract
10.1126/science.298.5594.824 ...
|
| |
Physical Review E (Statistical, Nonlinear, and Soft Matter Physics), Vol. 80, No. 4. (2009), 045102.
Abstract
The quantification of the complexity of networks is, today, a fundamental problem in the physics of complex systems. A possible roadmap to solve the problem is via extending key concepts of information theory to networks. In this Rapid Communication we propose how to define the Shannon entropy of a network ensemble and how it relates to the Gibbs and von Neumann entropies of network ensembles. The quantities we introduce here will play a crucial role for the formulation of null models ...
|
| |
Physical Review E (Statistical, Nonlinear, and Soft Matter Physics), Vol. 80, No. 5. (2009), 056103.
Abstract
Recently, the abundance of digital data is enabling the implementation of graph-based ranking algorithms that provide system level analysis for ranking publications and authors. Here, we take advantage of the entire Physical Review publication archive (1893–2006) to construct authors' networks where weighted edges, as measured from opportunely normalized citation counts, define a proxy for the mechanism of scientific credit transfer. On this network, we define a ranking method based on a diffusion algorithm that mimics the spreading of scientific credits on ...
|
| |
(23 Nov 2009)
Abstract
To identify communities in directed networks, we propose a generalized form of modularity in directed networks by introducing a new quantity LinkRank, which can be considered as the PageRank of links. This generalization is consistent with the original modularity in undirected networks and the modularity optimization methods developed for undirected networks can be directly applied to directed networks by optimizing our new modularity. Also, a model network, which can be used as a benchmark network in further community studies, is proposed to verify our method. Our method is ...
|
| |
Physica A: Statistical Mechanics and its Applications, Vol. 389, No. 3. (01 February 2010), pp. 577-586.
Abstract
We study how initial network structure affects the evolution of cooperation in a spatial prisoner’s dilemma game. The network structure is characterized by various statistical properties. Among those properties, we focus on the variance of the degree distribution, and inquire how it affects the evolution of cooperation by three methods of imitation. For every method, it was found that a scale-free network does not always promote the evolution of cooperation, and that there exists an appropriate value of the variance, at ...
|
| |
Physical Review Letters, Vol. 101, No. 14. (2008)
|
| |
(17 Nov 2008)
Abstract
Complex networks have acquired a great popularity in recent years, since the graph representation of many natural, social and technological systems is often very helpful to characterize and model their phenomenology. Additionally, the mathematical tools of statistical physics have proven to be particularly suitable for studying and understanding complex networks. Nevertheless, an important obstacle to this theoretical approach is still represented by the difficulties to draw parallelisms between network science and more traditional aspects of statistical physics. In this paper, we explore the relation between complex networks and a ...
|
| |
マルチエージェントシミュレーションの社会システムへの応用特集号
|
| |
Sociological Theory, Vol. 1 (1983), pp. 201-233.
Abstract
In this chapter I review empirical studies directly testing the hypotheses of my 1973 paper "The Strength of Weak Ties" (hereafter "SWT") and work that elaborates those hypotheses theoretically or uses them to suggest new empirical research not discussed in my original formulation. Along the way, I will reconsider various aspects of the theoretical argument, attempt to plug some holes, and broaden its base. ...
|