Complex Networks IV

Social networks such as Twitter or Facebook are part of the phenomenon called Big Data, a term used to describe very large and complex data sets. To represent these networks, the connections between users can be easily represented using (directed) graphs. In this paper, we are mainly focused on two different aspects of social network analysis. First, our goal is to find an efficient and high-level way to store and process a social network graph, using reasonable computing resources (processor and memory).We believe that this is an important research interest, since it provides a more democratic method to deal with large graphs.Next, we turn our attention to the study of social capitalists, a specific kind of users on Twitter. Roughly speaking, such users try to gain visibility by following other users regardless of their contents. Using two similarity measures called overlap index and ratio, we show that such users may be detected and classified very efficiently.

In ubiquitous and social web applications, there are different user traces, for example, produced explicitly by ”tweeting” via twitter or implicitly, when the corresponding activities are logged within the application’s internal databases and log files.

For each of these systems, the sets of user interactions can be mapped to a network, with links between users according to their observed interactions. This gives rise to a number of questions: Are these networks independent, do they give rise to a notion of user relatedness, is there an intuitively defined relation among users?

In this paper, we analyze correlations among different interaction networks among users within different systems. To address the questions of interrelationship between different networks, we collect for every user certain external properties which are independent of the given network structure. Based on these properties, we then calculate semantically grounded reference relations among users and present a framework for capturing semantics of user relations. The experiments are performed using different interaction networks from the twitter, flickr and BibSonomy systems.

This paper presents an academic web community, MathOverflow, as a network. Social network analysis is used to examine the interactions among users over a period of two and a half years.We describe relevant aspects associated with its behaviour as a result of the dynamics arisen from users participation and contribution, such as the existence of clusters, rich–club and collaborative properties within the network.We examine, in particular, the relationship between the social achievements obtained by users and node centrality derived from interactions through posting questions, answers and comments. Our study shows that the two aspects have a strong direct correlation; and active participation in the forum seems to be the most effective way to gain social recognition.

In this paper we present a framework to study evolution of communities in dynamic networks. A dynamic network is represented by a sequence of static graphs named as network snapshots.We introduce a distance measure between static graphs to study similarity among network snapshots and to detect outlier events. To find a detailed structure within each network snapshot we used a modularity maximization algorithm based on a fast greedy search extended with a random walk approach. Community detection often results in a different number of communities in different network snapshots. To make communities evolution studies feasible we propose a greedy method to match clustering labels assigned to different networks. The suggested framework is applied for analysis of dynamic networks built from real-world mobile datasets.

We live in a world where information flows very rapidly and people become aware of events on the other side of the world in a matter of seconds; this a consequence of the globalized, fully-connected world we live in. Information spreads via many different channels, but more recently we have witnessed the birth of the information-over-online-social-network phenomena. This means that more and more people get their news from online social networks such Facebook and microblogs such as Twitter. Yet, another source of information are weblogs (or blogs). Bloggers (people who write to blog or own a blog) are capable of influencing a lot of people and they even tend to be sources of information to mainstream news media. This paper delves into an issue relating to the ability of information to spread, but instead of tracking information itself, we look at the infrastructure that is in place linking blogs.We argue that the structure itself is an enabler or disabler of information spread depending on a categorization. This paper categorizes blogs and studies the level of overlap between these categories.

Research in the field of Opinion Dynamics studies how the distribution of opinions in a population of agents alters over time, as a consequence of interactions among the agents and/or in response to external influencing factors. One of most widely-cited items of literature in this field is a paper by Deffuant et al. (2002) introducing the Relative Agreement (RA) model of opinion dynamics, published in the Journal of Artificial Societies and Social Simulation (JASSS). In a recent paper published in the same journal, Meadows & Cliff (2012) questioned some of the results published in Deffuant et al. (2002) and released public-domain source-code for implementations of the RA model that follow the description given by Deffuant et al., but which generate results with some significant qualitative differences. The results published by Meadows & Cliff (2012) follow the methodology of Deffuant et al. (2002), simulating a population of agents in which, in principle, any agent can influence the opinion of any other agent. That is, the ”social network” of the simulated agents is a fully connected graph. In contrast, in this paper we report on the results from a series of empirical experiments where the social network of the agent population is non-trivially structured, using the stochastic network construction algorithm introduced by Klemm & Eguiluz (2002), which allows variation of a single real-valued control parameter μ _KE over the range [0,1], and which produces network topologies that have ”small world” characteristics when μ _KE =0 and that have ”scale free” characteristics when μ _KE =1. Using the public-domain source-code published in JASSS, we have studied the response of the dynamics of the RA model of opinion dynamics in populations of agents with complex social networks. Our primary findings are that variations in the clustering coefficient of the social networks (induced by altering μ _KE ) have a significant effect on the opinion dynamics of the RA model operating on those networks, whereas the effect of variations in average shortest path length is much weaker.

Social networks and social capital are generally considered to be important variables in explaining the diffusion of behavior. However, it is contested whether the actual social connections, cultural discourse, or individual preferences determine this diffusion. Using discrete choice analysis applied to longitudinal Twitter data, we are able to distinguish between social network influence on one hand and cultural discourse and individual preferences on the other hand. In addition, we present a method using freely available software to estimate the size of the error due to unobserved correlated effects. We show that even in a seemingly saturated model, the log likelihood can increase dramatically by accounting for unobserved correlated effects. Furthermore the estimated coefficients in an uncorrected model can be significantly biased beyond standard error margins.

We investigate a population of limit-cycle Kuramoto oscillators coupled in a complex network topology with coupling delays introduced by finite signal propagation speed and embedding in a ring. By numerical simulation we find that in complete graphs velocity waves arise that were not observed before and analytically not understood. In regular rings and small-world networks frequency synchronization occurs with a large variety of phase patterns. While all these patterns are nearly equally probable in regular rings, small-world topology sometimes prefers one pattern to form for a large number of initial conditions.We propose implications of this in the context of the temporal coding hypothesis for information processing in the brain and suggest future analysis to conclude the work presented here.

In the 19^th century Alphonse the Lamartine (1790-1869), a French writer, said that ”History Teaches Everything, Including the Future.” This is a very accurate statement; the definition of what makes whole nations, what characterizes patriotism, relates to the history of that particular place. This understanding about the importance of History has always been recognized by thinkers, philosophers and writers. However, historical facts are often source of controversies and debates. In this paper we have applied Network Science techniques to analyze a Social Network of the History of Brazil to create a rank of Historical Characters. To carry out such analyses we first have built a dataset based on Wikipedia text bodies using Natural Language Processing.

Air transport plays a crucial role for connecting people around the globe. Existing network studies often consider only flight networks. However, another important aspect of air transport is the passenger flow from origin to destination–a separate yet interdependent network. This study argues that for a comprehensive study of air transport, both aspects should be taken into account. These networks represent the structure and function of a complex system. The framework of function-structure networks provides a formal model to describe large-scale networked systems. To demonstrate the approach, the global and local properties of the function and structure of European air transport are investigated. This paper also proposes an adjusted betweenness centrality metric and other centrality metrics that can help explain anomalies found in previous investigations of air transportation systems.

Since clustering algorithms identify communities even in networks that are not believed to exhibit clustering behavior, we are interested in evaluating the significance of the communities returned by these algorithms. As a proxy for significance, prior work has investigated stability: by how much do the clusters change when the network is perturbed? We describe a cheap and simple method for evaluating stability and test it on a variety of real-world and synthetic graphs. Rather than evaluating our method on a single clustering algorithm, we give results using three popular clustering algorithms and measuring the distance between computed clusterings via three different metrics. We consider the results in the context of known strengths and weaknesses of the three clustering algorithms and also compare our method against that of measuring modularity. Finally we give evidence that our method provides more information than does the modularity.

We outline a method for constructing in parallel a collection of local clusters for a massive distributed graph. For a given input set of (vertex, cluster size) tuples, we compute approximations of personal PageRank vectors in parallel using Pregel, and sweep the results using MapReduce. We show our method converges to the serial approximate PageRank, and perform an experiment that illustrates the speed up over the serial method. We also outline a random selection and deconfliction procedure to cluster a distributed graph, and perform experiments to determine the quality of clusterings returned.

We propose a framework to unfold the ego-centered community structure of a given node in a network. The framework is not based on the optimization of a quality function, but on the study of the irregularity of the decrease of a similarity measure. It is a practical use of the notion of multi-ego-centered community and we validate the pertinence of the approach on a real-world network of wikipedia pages.

The smallest positive eigenvalue of the Laplacian of a network is called the spectral gap and characterizes various dynamics on networks. We propose mathematical programming methods to maximize the spectral gap of a given network by removing a fixed number of nodes. We formulate relaxed versions of the original problem using semidefinite programming and apply them to example networks.

Heterogeneous k-core percolation is an extension of a percolation model which has interesting applications to the resilience of networks under random damage. In this model, the notion of node robustness is local, instead of global as in uniform k-core percolation. One of the advantages of k-core percolation models is the validity of an analytical mathematical framework for a large class of network topologies. We study ternary mixtures of node types in random networks and show the presence of a new type of critical phenomenon. This scenario may have useful applications in the stability of large scale infrastructures and the description of glass-forming systems.

We introduce a quantitative measure of robustness of network controllability. Given a set of control nodes which drive the network, we investigate the effect of edge removal on the number of controllable nodes. We find that the mean degree of the network is a major factor in determining the robustness of random networks. Nonetheless, a comparison between real and random networks indicates a statistically significant difference which points to additional factors that influence the robustness of control of real complex networks.