Bolozna's library 95 articles

Abstract

We present a modeling framework for dynamical and bursty contact networks made of agents in social interaction. We consider agents’ behavior at short time scales in which the contact network is formed by disconnected cliques of different sizes. At each time a random agent can make a transition from being isolated to being part of a group or vice versa. Different distributions of contact times and intercontact times between individuals are obtained by considering transition probabilities with memory effects, i.e., the ...

Abstract

A large body of work has been devoted to defining and identifying clusters or communities in social and information networks. We explore from a novel perspective several questions related to identifying meaningful communities in large social and information networks, and we come to several striking conclusions. We employ approximation algorithms for the graph partitioning problem to characterize as a function of size the statistical and structural properties of partitions of graphs that could plausibly be interpreted as communities. In particular, we define the network community profile plot, which characterizes ...

Abstract

The study of complex networks sheds light on the relation between the structure and function of complex systems. One remarkable result is the absence of an epidemic threshold in infinite-size scale-free networks, which implies that any infection will perpetually propagate regardless of the spreading rate. The vast majority of current theoretical approaches assumes that infections are transmitted as a reaction process from nodes to all neighbors. Here we adopt a different perspective and show that the epidemic incidence is shaped by traffic flow conditions. Specifically, we consider the ...

Abstract

Several important complex network measures that helped discovering common patterns across real-world networks ignore edge weights, an important information in real-world networks. We propose a new methodology for generalizing measures of unweighted networks through a generalization of the cardinality concept of a set of weights. The key observation here is that many measures of unweighted networks use the cardinality (the size) of some subset of edges in their computation. For example, the node degree is the number of edges incident to a node. We define the effective cardinality, ...

Abstract

Hit songs, books, and movies are many times more successful than average, suggesting that "the best" alternatives are qualitatively different from "the rest"; yet experts routinely fail to predict which products will succeed. We investigated this paradox experimentally, by creating an artificial "music market" in which 14,341 participants downloaded previously unknown songs either with or without knowledge of previous participants' choices. Increasing the strength of social influence increased both inequality and unpredictability of success. Success was also only partly determined by ...

Abstract

Structurally segregated and functionally specialized regions of the human cerebral cortex are interconnected by a dense network of cortico-cortical axonal pathways. By using diffusion spectrum imaging, we noninvasively mapped these pathways within and across cortical hemispheres in individual human participants. An analysis of the resulting large-scale structural brain networks reveals a structural core within posterior medial and parietal cerebral cortex, as well as several distinct temporal and frontal modules. Brain regions within the structural core share high degree, strength, and betweenness ...

Abstract

We show that qualitatively different epidemic-like processes from distinct societal domains (finance, social and commercial blockbusters, epidemiology) can be quantitatively understood using the same unifying conceptual framework taking into account the interplay between the timescales of the grouping and fragmentation of social groups together with typical epidemic transmission processes. Different domain-specific empirical infection profiles, featuring multiple resurgences and abnormal decay times, are reproduced simply by varying the timescales for group formation and individual transmission. Our model emphasizes the need to account for the dynamic evolution of multi-connected networks. Our results ...

Abstract

Many real-world networks are so large that we must simplify their structure before we can extract useful information about the systems they represent. As the tools for doing these simplifications proliferate within the network literature, researchers would benefit from some guidelines about which of the so-called community detection algorithms are most appropriate for the structures they are studying and the questions they are asking. Here we show that different methods highlight different aspects of a network's structure and that the the sort of information that we seek to ...

Abstract

It has been shown that the communities of complex networks often overlap with each other. However, there is no effective method to quantify the overlapping community structure. In this paper, we propose a novel metric to address this problem. Instead of assuming that one node can only belongs to one community, our metric assumes that a maximal clique only belongs to one community. In this way, the overlaps between communities are allowed. Then, to identify the overlapping community structure, we construct a maximal clique network from the original ...

Abstract

A large number of complex systems find a natural abstraction in the form of weighted networks whose nodes represent the elements of the system and the weighted edges identify the presence of an interaction and its relative strength. In recent years, the study of an increasing number of large scale networks has highlighted the statistical heterogeneity of their interaction pattern, with degree and weight distributions which vary over many orders of magnitude. These features, along with the large number of elements and links, make the extraction of the ...

Note (first note only)

File sharing P2P protocol for sharing files in a social network. That is, the data only goes through your trusted friends. The paper uses Last.fm data to test how effective the protocol is in a real social network.

Abstract

We investigate the fundamental statistical features of tagged (or annotated) networks having a rich variety of attributes associated with their nodes. Tags (attributes, annotations, properties, features, etc.) provide essential information about the entity represented by a given node, thus, taking them into account represents a significant step towards a more complete description of the structure of large complex systems. Our main goal here is to uncover the relations between the statistical properties of the node tags and those of the graph topology. In order to better characterise the ...

Abstract

Many network problems are based on fundamental relationships involving time. Consider, for example, the problems of modeling the flow of information through a distributed network, studying the spread of a disease through a population, or analyzing the reachability properties of an airline timetable. In such settings, a natural model is that of a graph in which each edge is annotated with a time label specifying the time at which its endpoints “communicated.” We will call such a graph a ...

Abstract

Social networks are of interest to researchers in part because they are thought to mediate the flow of information in communities and organizations. Here we study the temporal dynamics of communication using on-line data, including e-mail communication among the faculty and staff of a large university over a two-year period. We formulate a temporal notion of "distance" in the underlying social network by measuring the minimum time required for information to spread from one node to another - a concept that ...

Abstract

We use real-world contact sequences, time-ordered lists of contacts from one person to another, to study how fast information or disease can spread across network of contacts. Specifically we measure the reachability time —the average shortest time for a series of contacts to spread information between a reachable pair of vertices (a pair where a chain of contacts exists leading from one person to the other)—and the reachability ratio —the fraction of reachable vertex pairs. These measures are studied ...

Abstract

Recent research using the complex network approach has revealed a rich and complicated network topology in the cortical connectivity of mammalian brains. It is of importance to understand the implications of such complex network structures in the functional organization of the brain activities. Here we study this problem from the viewpoint of dynamical complex networks. We investigate synchronization dynamics on the corticocortical network of the cat by modeling each node (cortical area) of the network with a sub-network of interacting excitable ...

Abstract

The connection matrix of the human brain (the human “connectome�) represents an indispensable foundation for basic and applied neurobiological research. However, the network of anatomical connections linking the neuronal elements of the human brain is still largely unknown. While some databases or collations of large-scale anatomical connection patterns exist for other mammalian species, there is currently no connection matrix of the human brain, nor is there a coordinated research effort to collect, archive, and disseminate this important information. We propose a ...

Abstract

Diffusion imaging can be used to estimate the routes taken by fiber pathways connecting different regions of the living brain. This approach has already supplied novel insights into in vivo human brain anatomy. For example, by detecting where connection patterns change, one can define anatomical borders between cortical regions or subcortical nuclei in the living human brain for the first time. Because diffusion tractography is a relatively new technique, however, it is important to assess its validity critically. We discuss the ...

Abstract

We found that personality characteristics are linked to dissociable connectivity streams in the human brain. Whereas fiber tracts between a subcortical network, including the hippocampus and amygdala, and the ventral striatum predicted individual differences in novelty seeking, tracts between prefrontal cortex and the striatum predicted individual differences in reward dependence. These findings suggest that the strength of limbic-striatal connectivity may, in part, underlie human personality traits. ...

Abstract

A new methodology based on Diffusion Weighted Magnetic Resonance Imaging (DW-MRI) and Graph Theory is presented for characterizing the anatomical connections between brain gray matter areas. In a first step, brain voxels are modeled as nodes of a non-directed graph in which the weight of an arc linking two neighbor nodes is assumed to be proportional to the probability of being connected by nervous fibers. This probability is estimated by means of probabilistic tissue segmentation and intravoxel white matter orientational distribution ...

Abstract

Intuitively, higher intelligence might be assumed to correspond to more efficient information transfer in the brain, but no direct evidence has been reported from the perspective of brain networks. In this study, we performed extensive analyses to test the hypothesis that individual differences in intelligence are associated with brain structural organization, and in particular that higher scores on intelligence tests are related to greater global efficiency of the brain anatomical network. We constructed binary and weighted brain anatomical networks in each ...

Abstract

Uncovering the community structure exhibited by real networks is a crucial step towards an understanding of complex systems that goes beyond the local organization of their constituents. Many algorithms have been proposed so far, but none of them has been subjected to strict tests to evaluate their performance. Most of the sporadic tests performed so far involved small networks with known community structure and/or artificial graphs with a simplified structure, which is very uncommon in real systems. Here we test several methods against a recently introduced class of ...

Abstract

Among the realistic ingredients to be considered in the computational modeling of infectious diseases, human mobility represents a crucial challenge both on the theoretical side and in view of the limited availability of empirical data. In order to study the interplay between small-scale commuting flows and long-range airline traffic in shaping the spatio-temporal pattern of a global epidemic we i) analyze mobility data from 29 countries around the world and find a gravity model able to provide a global description of commuting patterns up to 300 kms; ii) ...

Abstract

We develop a dynamical model for rewiring and attachment in bipartite networks in which edges are added between nodes that belong to fixed-size catalogs. We motivate this model with an empirical study of data from the video rental service Netflix, which invites its users to give ratings to the films available in its catalog. We find that the bipartite network that represents these data is tightly clustered and show that the distributions of the number of ratings given by users and the number of ratings received by ...

Abstract

The popularity of online social networks (OSNs) has given rise to a number of measurements studies that provide a first step towards their understanding. So far, such studies have been based either on complete data sets provided directly by the OSN itself or on Breadth-First-Search (BFS) crawling of the social graph, which does not guarantee good statistical properties of the collected sample. In this paper, we crawl the publicly available social graph and present the first unbiased sampling of Facebook (FB) users using a Metropolis-Hastings random walk with ...

Abstract

We use techniques from network science to study correlations in the foreign exchange (FX) market over the period 1991--2008. We consider an FX market network in which each node represents an exchange rate and each weighted edge represents a time-dependent correlation between the rates. To provide insights into the clustering of the exchange rate time series, we investigate dynamic communities in the network. We show that there is a relationship between an exchange rate's functional role within the market and its position within its community and use a ...

Abstract

Information cascades are phenomena in which individuals adopt a new action or idea due to influence by others. As such a process spreads through an underlying social network, it can result in widespread adoption overall. We consider information cascades in the context of recommendations, and in particular study the patterns of cascading recommendations that arise in large social networks. We investigate a large person-to-person recommendation network, consisting of four million people who made sixteen million recommendations on half a million products. ...

Abstract

Social psychologists have studied the psychological processes involved in persuasion, conformity, and other forms of social influence, but they have rarely modeled the ways influence processes play out when multiple sources and multiple targets of influence interact over time. However, workers in other fields from sociology and economics to cognitive science and physics have recognized the importance of social influence and have developed models of influence flow in populations and groups--generally without relying on detailed social psychological findings. This article reviews ...

Abstract

One important issue implied by the finite nature of real-world networks regards the identification of their more external (border) and internal nodes. The present work proposes a formal and objective definition of these properties, founded on the recently introduced concept of node diversity. It is shown that this feature does not exhibit any relevant correlation with several well-established complex networks measurements. A methodology for the identification of the borders of complex networks is described and illustrated with respect to theoretical (geographical and knitted networks) as well as real-world networks ...

Abstract

We study an extension of Axelrod's model for social influence, in which cultural drift is represented as random perturbations, while mass media are introduced by means of an external field. In this scenario, we investigate how the modular structure of social networks affects the propagation of mass media messages across the society. The community structure of social networks is represented by coupled random networks, in which two random graphs are connected by intercommunity links. Considering inhomogeneous mass media fields, we study the conditions for successful message spreading and ...

Abstract

Irreversible opinion spreading phenomena are studied on small-world and scale-free networks by means of the magnetic Eden model, a nonequilibrium kinetic model for the growth of binary mixtures in contact with a thermal bath. In this model, the opinion of an individual is affected by those of their acquaintances, but opinion changes (analogous to spin flips in an Ising-like model) are not allowed. We focus on the influence of advertising, which is represented by external magnetic fields. The interplay and competition between temperature and fields lead to order-disorder ...

Abstract

In the last few years we have witnessed the emergence, primarily in on-line communities, of new types of social networks that require for their representation more complex graph structures than have been employed in the past. One example is the folksonomy, a tripartite structure of users, resources, and tags -- labels collaboratively applied by the users to the resources in order to impart meaningful structure on an otherwise undifferentiated database. Here we propose a mathematical model of such tripartite structures which represents them as random hypergraphs. We show ...

Abstract

It is common to characterise networks based on their statistical properties. It has been shown that social networks, such as networks of co-starring film actors, collaborating scientists and email communicators, exhibit a positive first-order assortative behaviour, i.e. if two nodes are connected, then their degrees (the number of links a node has) are similar. For social networks, a node's degree has been assumed to be a proxy for its importance/prominence within the network, and the assortative behaviour is then interpreted as indicating that people mix with people of ...

Abstract

The characterization of the “most connected” nodes in static or slowly evolving complex networks has helped in understanding and predicting the behavior of social, biological, and technological networked systems, including their robustness against failures, vulnerability to deliberate attacks, and diffusion properties. However, recent empirical research of large dynamic networks (characterized by connections that are irregular and evolve rapidly) has demonstrated that there is little continuity in degree centrality of nodes over time, even when their degree distributions follow a power law. This unexpected dynamic centrality suggests that the connections ...

Abstract

Techniques for find document clusters mostly depend on models that impose strong explicit and/or implicit priori assumptions. As a consequence, the clustering effects tend to be unnatural and stray away from the intrinsic grouping natures of a document collection. We apply a novel graph-theoretic technique called Clique Percolation Method (CPM) for document clustering. In this method, a process of enumerating highly cohesive maximal document cliques is performed in a random graph, where those strongly adjacent cliques are mingled to form naturally ...

Abstract

Patterns of deliberate human activity and behavior are of utmost importance in areas as diverse as disease spread, resource allocation, and emergency response. Because of its widespread availability and use, e-mail correspondence provides an attractive proxy for studying human activity. Recently, it was reported that the probability density for the inter-event time $τ$ between consecutively sent e-mails decays asymptotically as $τ^-α$, with $α ≈ 1$. The slower than exponential decay of the inter-event time distribution suggests that deliberate human activity is inherently non-Poissonian. Here, we demonstrate that the approximate ...

Abstract

The existence of explosive phase transitions in random (Erdös Rényi-type) networks has been recently documented by Achlioptas, D’Souza, and Spencer [Science 323 , 1453 (2009)] via simulations. In this Letter we describe the underlying mechanism behind these first-order phase transitions and develop tools that allow us to identify (and predict) when a random network will exhibit an explosive transition. Several interesting new models displaying explosive transitions are also presented. ...

Abstract

There is much interest in the evolutionary forces that favored the evolution of large brains in the primate order. The social brain hypothesis posits that selection has favored larger brains and more complex cognitive capacities as a means to cope with the challenges of social life. The hypothesis is supported by evidence that shows that group size is linked to various measures of brain size. But it has not been clear how cognitive complexity confers fitness advantages on individuals. Research in ...

Abstract

10.1098/rstb.2006.2001 We present a detailed reanalysis of the comparative brain data for primates, and develop a model using path analysis that seeks to present the coevolution of primate brain (neocortex) and sociality within a broader ecological and life-history framework. We show that body size, basal metabolic rate and life history act as constraints on brain evolution and through this influence the coevolution of neocortex size and group size. However, they do not determine either of these variables, which appear to be ...

Abstract

The evolution of unusually large brains in some groups of animals, notably primates, has long been a puzzle. Although early explanations tended to emphasize the brain's role in sensory or technical competence (foraging skills, innovations, and way-finding), the balance of evidence now clearly favors the suggestion that it was the computational demands of living in large, complex societies that selected for large brains. However, recent analyses suggest that it may have been the particular demands of the more intense forms of ...

Abstract

Derenyi, Palla and Vicsek introduced the following dependent percolation model, in the context of finding communities in networks. Starting with a random graph $G$ generated by some rule, form an auxiliary graph $G'$ whose vertices are the $k$-cliques of $G$, in which two vertices are joined if the corresponding cliques share $k-1$ vertices. They considered in particular the case where $G=G(n,p)$, and found heuristically the threshold for a giant component to appear in $G'$. Here we give a rigorous proof of this result, as well as many extensions. ...

Abstract

Abstract When a computer network connects people or organizations, it is a social network. Yet the study of such computer-supported social networks has not received as much attention as studies of human-computer interaction, online person-to-person interaction, and computer-supported communication within small groups. We argue the usefulness of a social network approach for the study of computer-mediated communication. We review some basic concepts of social network analysis, describe how to collect and analyze social network data, and demonstrate where social network data ...

Abstract

We study random graph models for directed acyclic graphs, an important class of networks that includes citation networks, food webs, and feed-forward neural networks among others. We propose two specific models, roughly analogous to the fixed edge number and fixed edge probability variants of traditional undirected random graphs. We calculate a number of properties of these models, including particularly the probability of connection between a given pair of vertices, and compare the results with real-world acyclic network data finding that theory and measurements agree surprisingly well -- far better ...

Abstract

We analytically determine when a range of abstract social contagion models permit global spreading from a single seed on degree-correlated undirected random networks. We deduce the expected size of the largest vulnerable component, a network's tinderboxlike critical mass, as well as the probability that infecting a randomly chosen individual seed will trigger global spreading. In the appropriate limits, our results naturally reduce to standard ones for models of disease spreading and to the condition for the existence of a giant component. ...

Abstract

We model the mobility of mobile phone users to study the fundamental spreading patterns characterizing a mobile virus outbreak. We find that while Bluetooth viruses can reach all susceptible handsets with time, they spread slowly due to human mobility, offering ample opportunities to deploy antiviral software. In contrast, viruses utilizing multimedia messaging services could infect all users in hours, but currently a phase transition on the underlying call graph limits them to only a small fraction of the susceptible users. These results explain the lack of a major ...

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 in the human body. Detecting ...

Abstract

We use the concept of the network communicability (Phys. Rev. E 77 (2008) 036111) to define communities in a complex network. The communities are defined as the cliques of a communicability graph, which has the same set of nodes as the complex network and links determined by the communicability function. Then, the problem of finding the network communities is transformed to an all-clique problem of the communicability graph. We discuss the efficiency of this algorithm of community detection. In addition, we extend here the concept of the communicability ...

Abstract

Betweenness measures provide quantitative tools to pick out fine details from the massive amount of interaction data that is available from large complex networks. They allow us to study the extent to which a node takes part when information is passed around the network. Nodes with high betweenness may be regarded as key players that have a highly active role. At one extreme, betweenness has been defined by considering information passing only through the shortest paths between pairs of nodes. At the other extreme, an alternative type of ...

Abstract

We present a study of the properties of network of political discussions on one of the most popular Polish Internet forums. This provides the opportunity to study the computer mediated human interactions in strongly bipolar environment. The comments of the participants are found to be mostly disagreements, with strong percentage of invective and provocative ones. Binary exchanges (quarrels) play significant role in the network growth and topology. Statistical analysis shows that the growth of the discussions depends on the degree of controversy of the subject and the intensity ...