kubyaddi's library 125 articles

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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. ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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, ...

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 ...

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 ...

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, ...

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 ...

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 ...

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' ...

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 ...

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 ...

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 ...

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) ...

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. ...

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 ...

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 ...

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. ...

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 ...

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 ...

Abstract

10.1126/science.298.5594.824 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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. ...