Abstract

In many complex systems, elements interact via time-varying network topologies.Recent research shows that temporal correlations in the chronological ordering of interactions crucially influence network properties and dynamical processes.How these correlations affect our ability to control systems with time-varying interactions remains unclear. In this work, we use higher-order network models to extend the framework of structural controllability to temporal networks, where the chronological ordering of interactions gives rise to time-respecting paths with non-Markovian characteristics.We study six empirical data sets and show that non-Markovian characteristics of real systems can both increase or decrease the minimum time needed to control the whole system.With both empirical data and synthetic models, we further show that spectral properties of generalisations of graph Laplacians to higher-order networks can be used to analytically capture the effect of temporal correlations on controllability. Our work highlights that (i) correlations in the chronological ordering of interactions are an important source of complexity that significantly influences the controllability of temporal networks, and (ii) higher-order network models are a powerful tool to understand the temporal-topological characteristics of empirical systems.

Abstract

We propose a novel sequence prediction method for sequential data capturing node traversals in graphs. Our method builds on a statistical modelling framework that combines multiple higher-order network models into a single multi-order model. We develop a technique to fit such multi-order models in empirical sequential data and to select the optimal maximum order. Our framework facilitates both next-element and full sequence prediction given a sequence-prefix of any length. We evaluate our model based on six empirical data sets containing sequences from website navigation as well as public transport systems. The results show that our method out-performs state-of-the-art algorithms for next-element prediction. We further demonstrate the accuracy of our method during out-of-sample sequence prediction and validate that our method can scale to data sets with millions of sequences.

Abstract

The unsupervised detection of anomalies in time series data has important applications in user behavioral modeling, fraud detection, and cybersecurity. Anomaly detection has, in fact, been extensively studied in categorical sequences. However, we often have access to time series data that represent paths through networks. Examples include transaction sequences in financial networks, click streams of users in networks of cross-referenced documents, or travel itineraries in transportation networks. To reliably detect anomalies, we must account for the fact that such data contain a large number of independent observations of paths constrained by a graph topology. Moreover, the heterogeneity of real systems rules out frequency-based anomaly detection techniques, which do not account for highly skewed edge and degree statistics. To address this problem, we introduce HYPA, a novel framework for the unsupervised detection of anomalies in large corpora of variable-length temporal paths in a graph. HYPA provides an efficient analytical method to detect paths with anomalous frequencies that result from nodes being traversed in unexpected chronological order.

Abstract

Data from software repositories have become an important foundation for the empirical study of software engineering processes. A recurring theme in the repository mining literature is the inference of developer networks capturing e.g. collaboration, coordination, or communication from the commit history of projects. Most of the studied networks are based on the co-authorship of software artefacts. Because this neglects detailed information on code changes and code ownership we introduce git2net, a scalable python software that facilitates the extraction of fine-grained co-editing networks in large git repositories. It uses text mining techniques to analyse the detailed history of textual modifications within files. We apply our tool in two case studies using GitHub repositories of multiple Open Source as well as a commercial software project. Specifically, we use data on more than 1.2 million commits and more than 25'000 developers to test a hypothesis on the relation between developer productivity and co-editing patterns in software teams. We argue that git2net opens up a massive new source of high-resolution data on human collaboration patterns that can be used to advance theory in empirical software engineering, computational social science, and organisational studies.

Abstract

Data from software repositories have become an important foundation for the empirical study of software engineering processes. A recurring theme in the repository mining literature is the inference of developer networks capturing e.g. collaboration, coordination, or communication from the commit history of projects. Most of the studied networks are based on the co-authorship of software artefacts defined at the level of files, modules, or packages. While this approach has led to insights into the social aspects of software development, it neglects detailed information on code changes and code ownership, e.g. which exact lines of code have been authored by which developers, that is contained in the commit log of software projects. Addressing this issue, we introduce git2net, a scalable python software that facilitates the extraction of fine-grained co-editing networks in large git repositories. It uses text mining techniques to analyse the detailed history of textual modifications within files. This information allows us to construct directed, weighted, and time-stamped networks, where a link signifies that one developer has edited a block of source code originally written by another developer. Our tool is applied in case studies of an Open Source and a commercial software project. We argue that it opens up a massive new source of high-resolution data on human collaboration patterns.

Abstract

The inference of network topologies from relational data is an important problem in data analysis. Exemplary applications include the reconstruction of social ties from data on human interactions, the inference of gene co-expression networks from DNA microarray data, or the learning of semantic relationships based on co-occurrences of words in documents. Solving these problems requires techniques to infer significant links in noisy relational data. In this short paper, we propose a new statistical modeling framework to address this challenge. It builds on generalized hypergeometric ensembles, a class of generative stochastic models that give rise to analytically tractable probability spaces of directed, multi-edge graphs. We show how this framework can be used to assess the significance of links in noisy relational data. We illustrate our method in two data sets capturing spatio-temporal proximity relations between actors in a social system. The results show that our analytical framework provides a new approach to infer significant links from relational data, with interesting perspectives for the mining of data on social systems.

Abstract

In this manuscript, we show how higher-order graphical models can be applied to study the controllability of networked systems with dynamic topologies. Studying empirical data on temporal networks, we specifically show that the order correlations in the activation sequence of links can both increase or reduce the time needed to achieve full controllability. We then demonstrate how spectral properties of higher-order graphical models can be used to analytically explain the effect of order correlations on controllability in temporal networks.

Abstract

We introduce a framework for the modeling of sequential data capturing pathways of varying lengths observed in a network. Such data are important, e.g., when studying click streams in information networks, travel patterns in transportation systems, information cascades in social networks, biological pathways or time-stamped social interactions. While it is common to apply graph analytics and network analysis to such data, recent works have shown that temporal correlations can invalidate the results of such methods. This raises a fundamental question: when is a network abstraction of sequential data justified? Addressing this open question, we propose a framework which combines Markov chains of multiple, higher orders into a multi-layer graphical model that captures temporal correlations in pathways at multiple length scales simultaneously. We develop a model selection technique to infer the optimal number of layers of such a model and show that it outperforms previously used Markov order detection techniques. An application to eight real-world data sets on pathways and temporal networks shows that it allows to infer graphical models which capture both topological and temporal characteristics of such data. Our work highlights fallacies of network abstractions and provides a principled answer to the open question when they are justified. Generalizing network representations to multi-order graphical models, it opens perspectives for new data mining and knowledge discovery algorithms.

Abstract

In this article we study to what extent the academic peer review pro-cess is influenced by social relations between the authors of a manuscript and the editor handling the manuscript. Taking the Open Access journal PlosOne as a case study, our analysis is based on a data set of more than 100,000 articles pub-lished between 2007 and 2015. Using available data on handling editor, submission and acceptance time of manuscripts, we study the question whether co-authorship relations between authors and the handling editor affect the manuscript handling time, i.e. the time taken between the submission and acceptance of a manuscript. Our analysis reveals (i) that editors handle papers co-authored by previous col-laborators significantly more often than expected at random, and (ii) that such prior co-author relations are significantly related to faster manuscript handling. Addressing the question whether these shorter manuscript handling times can be explained by the quality of publications, we study the number of citations and downloads which accepted papers eventually accumulate. Moreover, we consider the influence of additional (social) factors, such as the editor’s experience, the top-ical similarity between authors and editors, as well as reciprocal citation relations between authors and editors. Our findings show that, even when correcting for other factors like time, experience, and performance, prior co-authorship relations have a large and significant influence on manuscript handling times, speeding up the editorial decision on average by 19 days.

Abstract

Statistical ensembles define probability spaces of all networks consistent with given aggregate statistics and have become instrumental in the analysis of relational data on networked systems. Their numerical and analytical study provides the foundation for the inference of topological patterns, the definition of network-analytic measures, as well as for model selection and statistical hypothesis testing. Contributing to the foundation of these important data science techniques, in this article we introduce generalized hypergeometric ensembles, a framework of analytically tractable statistical ensembles of finite, directed and weighted networks. This framework can be interpreted as a generalization of the classical configuration model, which is commonly used to randomly generate networks with a given degree sequence or distribution. Our generalization rests on the introduction of dyadic link propensities, which capture the degree-corrected tendencies of pairs of nodes to form edges between each other. Studying empirical and synthetic data, we show that our approach provides broad perspectives for community detection, model selection and statistical hypothesis testing.

Abstract

Recent research on temporal networks has highlighted the limitations of a static network perspective for our understanding of complex systems with dynamic topologies. In particular, recent works have shown that i) the specific order in which links occur in real-world temporal networks affects causality structures and thus the evolution of dynamical processes, and ii) higher-order aggregate representations of temporal networks can be used to analytically study the effect of these order correlations on dynamical processes. In this article we analyze the effect of order correlations on path-based centrality measures in real-world temporal networks. Analyzing temporal equivalents of betweenness, closeness and reach centrality in six empirical temporal networks, we first show that an analysis of the commonly used static, time-aggregated representation can give misleading results about the actual importance of nodes. We further study higher-order time-aggregated networks, a recently proposed generalization of the commonly applied static, time-aggregated representation of temporal networks. Here, we particularly define path-based centrality measures based on second-order aggregate networks, empirically validating that node centralities calculated in this way better capture the true temporal centralities of nodes than node centralities calculated based on the commonly used static (first-order) representation. Apart from providing a simple and practical method for the approximation of path-based centralities in temporal networks, our results highlight interesting perspectives for the use of higher-order aggregate networks in the analysis of time-stamped network data.

Abstract

Complex software development projects rely on the contribution of teams of developers, who are required to collaborate and coordinate their efforts. The productivity of such development teams, i.e., how their size is related to the produced output, is an important consideration for project and schedule management as well as for cost estimation. The majority of studies in empirical software engineering suggest that - due to coordination overhead - teams of collaborating developers become less productive as they grow in size. This phenomenon is commonly paraphrased as Brooks’ law of software project management, which states that “adding manpower to a software project makes it later”. Outside software engineering, the non-additive scaling of productivity in teams is often referred to as the Ringelmann effect, which is studied extensively in social psychology and organizational theory. Conversely, a recent study suggested that in Open Source Software (OSS) projects, the productivity of developers increases as the team grows in size. Attributing it to collective synergetic effects, this surprising finding was linked to the Aristotelian quote that “the whole is more than the sum of its parts”. Using a data set of 58 OSS projects with more than 580,000 commits contributed by more than 30,000 developers, in this article we provide a large-scale analysis of the relation between size and productivity of software development teams. Our findings confirm the negative relation between team size and productivity previously suggested by empirical software engineering research, thus providing quantitative evidence for the presence of a strong Ringelmann effect. Using fine-grained data on the association between developers and source code files, we investigate possible explanations for the observed relations between team size and productivity. In particular, we take a network perspective on developer-code associations in software development teams and show that the magnitude of the decrease in productivity is likely to be related to the growth dynamics of co-editing networks which can be interpreted as a first-order approximation of coordination requirements.

Abstract

We study properties of multi-layered, interconnected networks from an ensemble perspective, i.e. we analyze ensembles of multi-layer networks that share similar aggregate characteristics. Using a diffusive process that evolves on a multi-layer network, we analyze how the speed of diffusion depends on the aggregate characteristics of both intra- and inter-layer connectivity. Through a block-matrix model representing the distinct layers, we construct transition matrices of random walkers on multi-layer networks, and estimate expected properties of multi-layer networks using a mean-field approach. In addition, we quantify and explore conditions on the link topology that allow to estimate the ensemble average by only considering aggregate statistics of the layers. Our approach can be used when only partial information is available, like it is usually the case for real-world multi-layer complex systems.

Abstract

Large collaborative software engineering projects are interesting examples for evolving complex systems. The complexity of these systems unfolds both in evolving software structures, as well as in the social dynamics and organization of development teams. Due to the adoption of Open Source practices and the increasing use of online support infrastructures, large-scale data sets covering both the social and technical dimension of collaborative software engineering processes are increasingly becoming available. In the analysis of these data, a growing number of studies employ a network perspective, using methods and abstractions from network science to generate insights about software engineering processes. Featuring a collection of inspiring works in this area, with this topical issue, we intend to give an overview of state-of-the-art research. We hope that this collection of articles will stimulate downstream applications of network-based data mining techniques in empirical software engineering.

Abstract

Better understanding and controlling complex systems has become a grand challenge not only for computer science, but also for the natural and social sciences. Many of these systems have in common that they can be studied from a network perspective. Consequently methods from network science have proven instrumental in their analysis. In this article, I introduce the macroscopic perspective that is at the heart of network science. Summarizing my recent research activities, I discuss how a combination of this perspective with Big Data methods can improve our understanding of complex systems.

Abstract

Networked systems are becoming increasingly complex in development and operation. Due to this complexity, it is mostly impossible to follow a simple sequential design-deploy-use cycle. Instead, development and operation will become more evolutionary in nature. Additionally, one can observe that individual complex systems are coupled with each other, even though this has never been intended in the early development of these systems. As a result, we are facing interwoven systems – multiple open time-variant systems are coupled and interact having, e.g., different goals and objectives as well as changing system and communication structure. Based on and extending the idea of composing Systems of Systems, this article identifies challenges that are becoming increasingly apparent as the inevitable integration of systems progresses.

Abstract

The extraction of relevant knowledge from the increasingly large amount of information available in information repositories is one of the big challenges of our time. Although it is clear that the social and the information layer of collaborative knowledge spaces like the World Wide Web (WWW), scholarly publication databases or Online Social Networks (OSNs) are inherently coupled and thus inseparable, the question how the ranking and retrieval of information is influenced by the structure and dynamics of the social systems that create it has been addressed at most partially. In this talk, we will highlight associated research questions and challenges from an ethical, social and computer science perspective and introduce a multiplex network perspective that integrates both the social and the semantic layer of social information systems.

Abstract

We address the question to what extent the success of scientific articles is due to social influence. Analyzing a data set of over 100000 publications from the field of Computer Science, we study how centrality in the coauthorship network differs between authors who have highly cited papers and those who do not. We further show that a machine learning classifier, based only on coauthorship network centrality measures at time of publication, is able to predict with high precision whether an article will be highly cited five years after publication. By this we provide quantitative insight into the social dimension of scientific publishing - challenging the perception of citations as an objective, socially unbiased measure of scientific success.

Abstract

Modular design is a desirable characteristic of complex software systems that can significantly improve their comprehensibility, maintainability and thus quality. While many software systems are initially created in a modular way, over time modularity typically degrades as components are reused outside the context where they were created. In this paper, we propose an automated strategy to remodularize software based on move refactoring, i.e. moving classes between packages without changing any other aspect of the source code. Taking a complex systems perspective, our approach is based on complex networks theory applied to the dynamics of software modular structures and its relation to an n-state spin model known as the Potts Model. In our approach, nodes are probabilistically moved between modules with a probability that nonlinearly depends on the number and module membership of their adjacent neighbors. The latter are defined by the underlying network of software dependencies. To validate our method, we apply it to a dataset of 39 Java open source projects in order to optimize their modularity. Comparing the source code generated by the developers with the optimized code resulting from our approach, we find that modularity (i.e. quantified in terms of a standard measure from the study of complex networks) improves on average by 166+-77 percent. In order to facilitate the application of our method in practical studies, we provide a freely available Eclipse plug-in.

Abstract

Enterprise social software tools are increasingly being used to support the communication and collaboration between employees, as well as to facilitate the collaborative organisation of information and knowledge within companies. Not only do these tools help to develop and maintain an efficient social organisation, they also produce massive amounts of fine-grained data on collaborations, communication and other forms of social relationships within an enterprise. In this chapter, we argue that the availability of these data provides unique opportunities to monitor and analyse social structures and their impact on the success and performance of individuals, teams, communities and organisations. We further review methods from the planning, design and optimisation of telecommunication networks and discuss challenges arising when wanting to apply them to optimise the structure of enterprise social networks.

Abstract

Recent research has highlighted limitations of studying complex systems with time-varying topologies from the perspective of static, time-aggregated networks. Non-Markovian characteristics resulting from the ordering of interactions in temporal networks were identified as one important mechanism that alters causality and affects dynamical processes. So far, an analytical explanation for this phenomenon and for the significant variations observed across different systems is missing. Here we introduce a methodology that allows to analytically predict causality-driven changes of diffusion speed in non-Markovian temporal networks. Validating our predictions in six data sets we show that compared with the time-aggregated network, non-Markovian characteristics can lead to both a slow-down or speed-up of diffusion, which can even outweigh the decelerating effect of community structures in the static topology. Thus, non-Markovian properties of temporal networks constitute an important additional dimension of complexity in time-varying complex systems.

Abstract

When exploring the structure and function of such complex systems, the visualization of network topologies has become a standard technique. Many - if not most - of the systems being considered are inherently dynamic and in recent years more and more data on their dynamics are becoming available in the form of so-called temporal networks. We propose a simple mechanism that can be used to include temporal correlations present in longitudinal data on temporal networks in the layout of time-aggregated network structures. We particularly focus on non-Markovian properties of contact sequences in temporal networks, i.e. the fact that future contacts not only depend on the current contact, but also on past contacts. We demonstrate our approach by visualising a set of examples for temporal networks with non-Markovian properties. The visualisations show that the resulting visualizations reveal important aspects like e.g. community structures of the dynamics which - although present in empirical data sets - a) are not represented in static, aggregate networks and b) cannot easily be seen even in dynamic visualizations of temporal networks.

Abstract

We study the role of hierarchical structures in a simple model of collective consensus formation based on the bounded confidence model with continuous individual opinions. For the particular variation of this model considered in this paper, we assume that a bias towards an extreme opinion is introduced whenever two individuals interact and form a common decision. As a simple proxy for hierarchical social structures, we introduce a two-step decision making process in which in the second step groups of like-minded individuals are replaced by representatives once they have reached local consensus, and the representatives in turn form a collective decision in a downstream process. We find that the introduction of such a hierarchical decision making structure can improve consensus formation, in the sense that the eventual collective opinion is closer to the true average of individual opinions than without it. In particular, we numerically study how the size of groups of like-minded individuals being represented by delegate individuals affects the impact of the bias on the final population-wide consensus. These results are of interest for the design of organisational policies and the optimisation of hierarchical structures in the context of group decision making.

Abstract

The goal of human resource management is to ensure an effective company environment. Crucial for a good corporate culture is a comfortable atmosphere and positive social relationships between the employees. The interactions of the people and groups working in the company define their relationships and are reflected in the company's social network. Projections of such networks are Enterprise Social Networks which are more and more integrated in companies. These social networks can be a powerful tool to analyse the structure of a company and indicate potential problems. This extended abstract poses research questions to identify and quantify mechanisms that have an impact on the social network of a company to ensure resilience. To address these questions we make assumptions based on real-world observations for a subsequent model.

Abstract

Efficient bug triaging procedures are an important precondition for successful collaborative software engineering projects. Triaging bugs can become a laborious task particularly in open source software (OSS) projects with a large base of comparably inexperienced part-time contributors. In this paper, we propose an efficient and practical method to identify valid bug reports which a) refer to an actual software bug, b) are not duplicates and c) contain enough information to be processed right away. Our classification is based on nine measures to quantify the social embeddedness of bug reporters in the collaboration network. We demonstrate its applicability in a case study, using a comprehensive data set of more than 700, 000 bug reports obtained from the BUGZILLA installation of four major OSS communities, for a period of more than ten years. For those projects that exhibit the lowest fraction of valid bug reports, we find that the bug reporters’ position in the collaboration network is a strong indicator for the quality of bug reports. Based on this finding, we develop an automated classification scheme that can easily be integrated into bug tracking platforms and analyze its performance in the considered OSS communities. A support vector machine (SVM) to identify valid bug reports based on the nine measures yields a precision of up to 90.3% with an associated recall of 38.9%. With this, we significantly improve the results obtained in previous case studies for an automated early identification of bugs that are eventually fixed. Furthermore, our study highlights the potential of using quantitative measures of social organization in collaborative software engineering. It also opens a broad perspective for the integration of social network analysis in the design of support infrastructures.

Abstract

Social organization and division of labor crucially influence the performance of collaborative software engineering efforts. In this paper, we provide a quantitative analysis of the relation between social organization and performance in Gentoo, an Open Source community developing a Linux distribution. We study the structure and dynamics of collaborations as recorded in the project's bug tracking system over a period of ten years. We identify a period of increasing centralization after which most interactions in the community were mediated by a single central contributor. In this period of maximum centralization, the central contributor unexpectedly left the project, thus posing a significant challenge for the community. We quantify how the rise, the activity as well as the subsequent sudden dropout of this central contributor affected both the social organization and the bug handling performance of the Gentoo community. We analyze social organization from the perspective of network theory and augment our quantitative findings by interviews with prominent members of the Gentoo community which shared their personal insights.

Abstract

The study of complex networks and collective dynamics occurring in biological, social and technical systems has experienced a massive surge of interest both from academia and industry. Many of the results on the mechanisms underlying the self-organized formation of complex dynamic networks in natural and man-made systems have been derived based on a statistical physics perspective. In this tutorial, we provide a basic introduction to this perspective which will help attendees to benefit from the vast literature on self-organization and self-adaptation phenomena available in the fields of network science and complex systems. We cover basic models and abstractions for the study of static complex networks as well as dynamical processes like, e.g., information diffusion, random walks, synchronization or the propagation of cascading failures. We further introduce recent advances in the study of dynamic (social) networks and demonstrate how the resulting methods can be practically applied in the engineering of self-organizing and self-adaptive distributed systems and protocols.

Abstract

Time-evolving interaction patterns studied in different contexts can be well represented bytemporal networks in which nodes are intermittently connected. In this Letter we introducethe notion of betweenness preference in the study of temporal networks. It captures how likelya certain node is to mediate interactions between particular pairs of its neighboring nodes.We argue that betweenness preference is an important correlation to consider in the analysisof temporal network data. In particular, it allows to assess to which extent paths existing intime-aggregated, static representations of temporal networks are actually feasible based onthe underlying sequence of interactions. We argue that betweenness preference correlationsare present in empirical data sets. We further show that neglecting betweenness preferencewill lead to significantly wrong statements about spreading dynamics in temporal networks.

Abstract

The vision of Organic Computing addresses challenges that arise in the design of future information systems that are comprised of numerous, heterogeneous, resource-constrained and error-prone components. The notion organic highlights the idea that, in order to be manageable, such systems should exhibit self-organization, self-adaptation and self-healing characteristics similar to those of biological systems. In recent years, the principles underlying these characteristics are increasingly being investigated from the perspective of complex systems science, particularly using the conceptual framework of statistical physics and statistical mechanics. In this article, we review some of the interesting relations between statistical physics and networked systems and discuss applications in the engineering of organic overlay networks with predictable macroscopic properties.

Abstract

In this paper, we propose a simple randomized protocol for identifying trusted nodes based on personalized trust in large scale distributed networks. The problem of identifying trusted nodes, based on personalized trust, in a large network setting stems from the huge computation and message overhead involved in exhaustively calculating and propagating the trust estimates by the remote nodes. However, in any practical scenario, nodes generally communicate with a small subset of nodes and thus exhaustively estimating the trust of all the nodes can lead to huge resource consumption. In contrast, our mechanism can be tuned to locate a desired subset of trusted nodes, based on the allowable overhead, with respect to a particular user. The mechanism is based on a simple exchange of random walk messages and nodes counting the number of times they are being hit by random walkers of nodes in their neighborhood. Simulation results to analyze the effectiveness of the algorithm show that using the proposed algorithm, nodes identify the top trusted nodes in the network with a very high probability by exploring only around 45% of the total nodes, and in turn generates nearly 90% less overhead as compared to an exhaustive trust estimation mechanism, named TrustWebRank. Finally, we provide a measure of the global trustworthiness of a node; simulation results indicate that the measures generated using our mechanism differ by only around 0.6% as compared to TrustWebRank.

Abstract

The success of open source projects crucially depends on the voluntary contributions of a suf- ficiently large community of users. Apart from the mere size of the community, interesting questions arises when looking at the evolution of structural features of collaborations between community members. In this article, we discuss several network analytic proxies that can be used to quantify different aspects of the social organisation in social collaboration networks. We particularly focus on measures that can be related to the cohesiveness of the communities, the distribution of responsibilities and the resilience against turnover of community members. We present a comparative analysis on a large-scale data set that covers the full history of collabor- ations between users of 14 major open source software communities. Our analysis covers both aggregate and time-evolving measures and highlights differences in the social organisation across communities. We argue that our results are a promising first step towards the definition of suitable, potentially multi-dimensional, resilience and risk indicators for open source software communities.

Abstract

We study the role of hierarchical structures in a simple model of collective consensus formation based on the bounded confidence model with continuous individual opinions. For the particular variation of this model considered in this paper, we assume that a bias towards an extreme opinion is introduced whenever two individuals interact and form a common decision. As a simple proxy for hierarchical social structures, we introduce a two-step decision making process in which in the second step groups of like-minded individuals are replaced by representatives once they have reached local consensus, and the representatives in turn form a collective decision in a downstream process. We find that the introduction of such a hierarchical decision making structure can improve consensus formation, in the sense that the eventual collective opinion is closer to the true average of individual opinions than without it. In particular, we numerically study how the size of groups of like-minded individuals being represented by delegate individuals affects the impact of the bias on the final population-wide consensus. These results are of interest for the design of organisational policies and the optimisation of hierarchical structures in the context of group decision making.

Abstract

When dealing with networks of several kind, network theory provides the theoretical framework and the practical tools to analyze them. Mostly analysis focuses on steady networks, i.e. networks with fixed topology. However, real-world scenarios often deal with (highly) dynamic topologies. As of today, the question of how to investigate such scenarios, e.g. defining a meaningful notion of “temporal centrality”, has generally not been answered. In this poster we present research pointing out the obstacles arising in this endeavor as well as a possible framework to address those issues, which we call time-explicit graphs.

Abstract

Today social networks and microblogging services attract much attention and their importance and pervasion is constantly increasing. This trend is fostered by the increasing prevalence of mobile internet devices, which enable users to be online every time and everywhere. A popular kind of applications provided via social network platforms are games. While existing social network games basically realize common online game principles where each user controls a single game entity and acts on its own behalf, this paper presents a framework for the creation of a novel kind of social online games. The idea is to enable games where users do not act as individual game entities, instead groups of users control one game entity whose behavior emerges from the collective behavior of all group members. The framework is based on the microblogging service Twitter and users interact with the game via Twitter messages. These collaborative social online games are not just an innovative social network application, the intention of our framework is rather to provide a useful and powerful tool to complex social network researchers to study emergent and collective user behavior on a large scale utilizing the huge user base of a social network service like Twitter. In addition to presenting the idea of collaborative social online games along with the so-called TweetGame framework, this paper presents a sample application that has already been realized on top of this framework as proof of concept.

Abstract

In this article, we present and evaluate an epidemic scheme for the synchronization of coupled Kuramoto oscillators in communication networks. It addresses the problem of efficiently providing globally synchronous time epochs in complex, dynamic Peer-to-Peer network topologies. Rather than the usual model of continuously coupled nodes, a discretized version with sporadic message-based couplings to nearest neighbors is considered. This article empirically studies the emergence of coherent oscillator states for different network topologies, coupling functions, and sporadic coupling intensities. It further investigates the protocol's minimum bandwidth requirements in small-world network topologies. Synchronization resilience under the effect of random perturbations is studied for two coupling variations. Finally, the potential utilization of the scheme for a local inference of global network topology characteristics is discussed.

Abstract

When dealing with dynamic large-scale topologies such as those underlying Peer-to-Peer (P2P) Distributed Virtual Environments (DVEs), one inescapably reaches the point where either: a) simulations lack human behaviour and assessment or where b) practical experiments on a small scale do not yield significant results. The restrictions resulting from the separation of simulation and testbed environments hinder a comprehensive assessment and efficient development of adaptive algorithms and techniques for DVEs as they are investigated in our HyperVerse research project. In this paper, we present a hybrid evaluation system designed to combine the advantages of simulations and testbeds. The proposed infrastructure exhibits great flexibility particularly alluring in view of the multitude of potential research in the context of DVEs.

Abstract

With the growth of Massively Multiuser Virtual Environments (MMVEs) and increasingly interactive social networking platforms, it is widely accepted that their convergence renders today’s centralized hosting approaches impracticable. To handle virtual environments of such massive scale, decentralized systems are necessary that also involve the resources of clients. The expedient design of techniques enabling this kind of next-generation decentralized distributed virtual environments (DDVEs) is a growing field of research. In the HyperVerse project, we aim at the provision of an infrastructure enabling such DDVEs, focusing on collaboration and self-organization as means to achieve a maximum degree of scalability. In this paper we present a self-organized resource allocation scheme for DDVEs functioning independent of the underlying P2P network topology. Exploiting the heterogeneity of clients and utilizing locally available information only, it helps alleviate the load imposed by regions with a high user density as they often occur in such environments. Evaluations show that both for the discovery of these regions and their alleviation the local views converge fast to a global one, with favorable effects on the overlay topology.

Abstract

Random scale-free overlay topologies provide a number of properties like for example high resilience against failures of random nodes, small (average) diameter as well as good expansion and congestion characteristics that make them interesting for the use in large-scale distributed systems. A number of these properties have been shown to be influenced by the exponent of their power law degree distribution. In this article, we present a distributed rewiring scheme that is suitable to effectuate random scale-free overlay topologies with an adjustable degree distribution exponent. The scheme uses a biased random walk strategy to sample new endpoints of edges being rewired and relies on an equilibrium model for scale-free networks. The bias of the random walk strategy can be tuned to produce random scale-free networks with arbitrary degree distribution exponents greater than two. We argue that the rewiring strategy can be implemented in a distributed fashion based on a node's information about its immediate neighbors. We present both analytical arguments as well as results that have been obtained in simulations of the proposed protocol.

Abstract

The idea of the 3D Web as a global scale Distributed Virtual Environment (DVE) currently is very popular and a lot of research work is done in this field. In the course of the HyperVerse project we have developed a two-tier Peer-To-Peer (P2P) architecture as basic infrastructure for a federated, open and scalable 3D Web. Our approach relies on a concept that incorporates a loosely-structured P2P network overlay of user clients and a highly-structured overlay that connects a federation of reliable server machines constituting a reliable backbone service. A central problem when intending to build a massive virtual online environment is how avatar interaction as well as tracking and provision of avatar positions can be realized in a globally scalable manner. This paper presents a hybrid avatar interaction scheme developed for HyperVerse that incorporates the user clients and the backbone service for avatar position tracking. The backbone is used as reliable fall-back service, while the avatar tracking is handled in a pure P2P fashion whenever possible. This way backbone overload is prevented in a self-organizing manner whenever client density tends to overburden the backbone infrastructure.

Abstract

Massive Multiuser Virtual Environments (MMVEs) and the idea of a global scale 3D Web have grown popular in recent years. While commercial precursors of such environments for the most part rely on centralized client/server architectures, it is commonly accepted that a global scale virtual online world can only be realized in a distributed fashion. Within the HyperVerse project, we have developed and recently presented a two-tier Peer-to-Peer (P2P) architecture that incorporates a loosely structured P2P overlay of user peers and a highly structured overlay of server machines constituting a reliable backbone service. In such a distributed environment, an essential question is how avatars are tracked and interconnected in order to allow mutual rendering and interaction. We have previously proposed a hybrid avatar management scheme that utilizes the backbone service for avatar tracking if necessary, but handles tracking in a P2P fashion when peers can track each other to reduce the backbone load. This paper presents a detailed performance analysis of this algorithm under a realistic scenario, using traces from a large scale MMVE called Second Life. Moreover this paper presents and evaluates an optimization for the hybrid avatar tracking scheme that can be utilized under a weaker condition.

Abstract

Due to the huge amount of available information in today's society, it becomes more and more difficult for the consumer to locate the most useful information for a specific topic. Recommender systems using collaborative filtering (CF) are a popular technique for reducing information overload and finding useful information on the Internet. However, in massive global-scale multi-user virtual environments different approaches are required from those used within the currently dominant centralized infrastructures or lately investigated P2P approaches. Within this paper we present a novel collaborative filtering algorithm used within the HyperVerse -- a P2P-based self-organizing middleware service for massively distributed virtual worlds -- to generate and manage recommendations for HyperVerse object favorites. Due to its global extent considering users and possible ratings, using a monolithic database-backed recommendation service or huge profile- or item-rating-matrices does not scale in our scenario. The decentralized approach presented within this paper creates per user ratings in an adaptive and transparent way by comparing public favorites of passer-by users with personal peer data, weighted by self-adjusting buddy lists.

Abstract

In distributed virtual environments, where avatars permanently change their properties (e.g. their position) or perform modifications on shared objects, inconsistent states may occur due to message latency or concurrent updates. Here, the consistency often falls prey to high interactivity and responsiveness demands. To minimize the presence of inconsistent states or data, the Elastic Consistency model aims at providing an optimal trade-off between consistency and system responsiveness. In this paper we present a Fuzzy Logic driven approach for the computation of this trade-off on the basis of environmental characteristics at the application runtime. Furthermore, we evaluate the impacts of this parameter on consistency and system responsiveness by adjusting the behavior of a classic mutual exclusion algorithm. In this paper we show that an acceptable degree of consistency with respect to required system responsiveness can be efficiently achieved, even when addressing a large number of users.

Abstract

In this article we present and evaluate an epidemic algorithm for the synchronization of coupled Kuramoto oscillators in complex network topologies. The algorithm addresses the problem of providing a global, synchronous notion of time in complex, dynamic Peer-to-Peer topologies. For this it requires a periodic coupling of nodes to a single random one-hop-neighbor. The strength of the nodes’ couplings is given as a function of the degrees of both coupling partners. We study the emergence of self-synchronization and the resilience against node failures for different coupling strength functions and network topologies. For Watts/Strogatz networks, we observe critical behavior suggesting that small-world properties of the underlying topology are crucial for self-synchronization to occur. From simulations on networks under the effect of churn, we draw the conclusion that special coupling functions can be used to enhance synchronization resilience in power-law Peer-to-Peer topologies.

Abstract

During the last few years the application scope of peer-to-peer systems has been notably extended. While the problems of scalable data localization have been exhaustively addressed, one may notice that the problem of multicast cost and latency delays in very large, global scale peer-to-peer networks still remains inadequately considered. Many large scale applications will suffer from this multicast cost if the number of users increases. In order to address this problem, we introduce HiOPS - a hierarchical two tier peer-to-peer system which provides a reasonable tradeoff between minimization of multicast cost and latency delays and reduction of maintenance and management cost. Because of its properties and characteristics HiOPS can be considered as a basic infrastructure for a wide range of peer-to-peer applications.

Abstract

Distributed virtual environments like online games or 3D virtual worlds have become very popular in the last few years and a more substantial surge in popularity and use is expected. Because of the huge number of users, such environments will undergo a change of infrastructure from a centralized to a decentralized one, making higher demands on consistency issues. This paper addresses consistency problems which may occur in distributed virtual environments and introduces the elastic consistency model to tackle these problems. According to elastic consistency, different consistency levels setting up a trade-off between consistency and responsiveness of the environment should be introduced in order to provide an efficient way of interaction on a global scale.

Abstract

Der zunehmende Gewinn an Bedeutung und Akzeptanz von Algorithmenvisualisierungssystemen (AVS) - sowohl bei Lernenden als auch bei Lehrenden - führt zu deren verstärkten Einsatz in der Lehre als moderne E-Learning-Instrumente. Während für viele Algorithmen eine zweidimensionale Visualisierung aus didaktischen Gründen vollkommen ausreicht, existieren zahlreiche Algorithmen, z. B. aus den Bereichen der Computergrafik und Bioinformatik, deren wesentliche Eigenschaften erst bei einer Visualisierung im Dreidimensionalen zur Geltung kommen. Da fast alle derzeit existierenden AVS sich jedoch auf die zweidimensionale Visualisierung von konventionellen Algorithmen und Datenstrukturen beschränken, entwickelten wir an unserem Institut einen XML-Standard (Auszeichnungssprache) [Th07, Ka05] zur dreidimensionalen Animation von Algorithmen und Datenstrukturen und stellen diesen in dieser Arbeit vor. Unser Hauptaugenmerk richtet sich dabei auf die Anwendbarkeit für rechenintensive und NP-vollständige Algorithmen [We03]. Nach einer kurzen Einführung in die Thematik und Motivation unserer Arbeit, gehen wir im zweiten Abschnitt auf die Ergebnisse unser Anforderungsund Stateof-the-Art-Analysen ein. Im darauffolgenden Abschnitt stellen wir die Struktur, den Aufbau und die Bestandteile sowie einige Features der von uns entwickelten Auszeichnungssprache (bzw. Standard) xml3DVis vor. Anschließend erfolgt eine Beschreibung des von uns implementierten Interpreters, mit dem in xml3DVis erstellte Skripte geparst, interpretiert und visuell dargestellt werden können. Im vorletzten Abschnitt zeigen wir anhand eines rechts aufwendigen Beispiels, wie wir mithilfe unserer Sprache das NP-vollständige Travelling-Salesman-Problem animiert haben. Abschließend evaluieren wir die Sprache und zeigen ein überraschendes Ergebnis.

Abstract

Massive Multiuser Virtual Environments (MMVEs) and especially the idea of a ''3D Web'' as a combination of a MMVE and today's WWW currently attracts a lot of attention. The realization of such a vision on a global scale though poses severe technical challenges to the underlying network infrastructure. It is generally accepted that such a global scale scenario can only be realized in a distributed fashion. The HyperVerse project aims at the provision of a federated global scalable infrastructure for such a ''3D Web'' scenario. We propose a two-tier Peer-to-Peer infrastructure that combines a loosely structured overlay network of user clients with a highly-structured overlay network of reliable so-called Public Servers constituting the backbone of our architecture. This paper presents the Grid-based Plane Partitioning Protocol (GP3), a structured Peer-to-Peer overlay network for the interconnection of the Public Servers that realizes a spatial index in order to allow fast location based queries.

Abstract

The ATLAS event monitoring service (Emon) is a CORBA-based peer-to-peer data distribution framework, which has been implemented for ATLAS-one of CERN's forthcoming particle physics experiments. Its purpose is to sample collision event data from various stages of the data flow chain and efficiently distribute them to the users. This paper discusses various technical details of the current peer-to-peer-based implementation. A special focus lies on dependability and the provision of scalability and predictable performance. A comparative study of message complexity and scalability as well as practical test results obtained during the HLT/DAQ large scale and performance test periods in July 2005 and November 2006 will be presented. Apart from that, a recent addition that facilitates the parallel analysis of event data on a set of machines will be presented.

Abstract

Distributed Virtual Environments (DVEs) have grown popular in various fields of application. Apart from providing great collaborational opportunities in an immersive setting, large-scale DVEs pose severe scalability challenges. Although P2P approaches have proven to be effective for tackling many of these issues, still load delay problems remain in regions with high object or avatar density. In this article we present and evaluate a hoarding approach that is suitable to minimize such delays in P2P-based DVEs with a real-time distribution of dynamic data. The prediction of what data shall be hoarded is based on an epidemic aggregation algorithm working solely with local knowledge. Evaluation results that have been obtained using a DVE simulation environment will be presented.

Abstract

In order to realistically simulate algorithms or evaluate P2P overlay topologies, a detailed model of the underlying router topology is required. Since actively measuring this topology is extremely laborious and furthermore a waste of network resources, traditionally topology generators are used in or- der to create synthetic router-level graphs. For this, usually graph models are selected that are known to generate graphs which are similar to the actual Internet in respect to a cer- tain metric like e.g. vertex degree distribution. These mod- els are often superseded or adjusted when new metrics are being introduced which better differentiate between graphs. Furthermore it has been shown, that graphs that are simi- lar in respect to e.g. vertex degree distribution can be very different from a structural point of view. In this paper Top- Gen, a generic, extensible and easy-to-use topology genera- tion platform is presented. It contains a topology generation module which bases the generation of router-level graphs on the Internet’s underlying principles and the technological constraints of routers rather than trying to effectuate sim- ilarity in respect to a certain metric. Apart from describ- ing TopGen’s general topology generation approach, graphs created with its Internet topology module are evaluated and found to be encouragingly similar to real-world datasets in various respects.

Abstract

Recent research in the field of complex networks has shown that-beyond microscopic structural qualities-global statistical parameters are sufficient to describe a surprising number of their macroscopic properties. This article argues that such statistical parameters can be monitored by nodes in a decentralized and efficient way. The so achieved awareness of a network's global parameters can be used by nodes for actively influencing them to optimize relevant characteristics of the overall network. For such an adaptation, the network-analogy of "phase transitions" in physical systems can be used. In this article the general concept of such an awareness-driven statistical adaptation is presented using power law networks as an example. For this important class of networks practical algorithms are introduced: Based on recent advances in reliable power law fitting, a gossip scheme has been developed which is suitable to make individual nodes aware of a power law network's critical exponent. In order to influence this parameter, decentralized reconnection rules are presented. The combination of both strategies facilitates a feedback control of large scale systems' emergent power law properties.

Abstract

A substantial number of massive large-scale applications require scalable underlying network topologies. Nowadays structured Peer-to-Peer overlay networks meet these requirements very well. But there is still a need to decide which of these overlay networks is most suitable for providing the best possible performance for a certain application. This paper describes SimCon-a simulation environment for overlay networks and large-scale applications. SimCon allows the comparison of different overlay networks with respect to predefined metrics derived from requirements of the considered application. This approach allows determining which overlay network meets the needs of a given application best, which in turn is a great support for developers of large-scale applications.

Abstract

The vision of a '3D Web' as a combination of massive online virtual environments and today's WWW currently attracts a lot of attention. While it provides a multitude of opportunities, the realisation of this vision on a global scale poses severe technical challenges. This paper points out some of the major challenges and highlights key concepts of an infrastructure that is being developed in order to meet them. Among these concepts, special emphasis is put on the usage of a two-tier Peer-to-Peer approach, the implementation of Torrent-based data distribution, and the development of a graded consistency notion. The paper presents the current state of a prototype implementation that is being developed in order to validate these concepts and evaluate alternative approaches.

Abstract

Currently one can see a surge of evolving technologies supporting the creation of Rich Internet Applications. All of these approaches however traditionally address the classic Client/Server scenario in which a dedicated Web Server acts as application provider for thin clients. This paper argues, that there are many scenarios in which a Peer-to-Peer approach enabling every application/process to export parts of its graphical user interface in a lightweight and interoperable way would be more desirable. This work-in-progress paper presents the lightweight middleware prototype SEMPA, proving that these scenarios can be supported by combining the readily available technologies eXtensible Application Markup Language (XAML) and Web Services.

Abstract

Starting from the classical Client/Server paradigm, in the last couple of years Peer-To-Peer approaches have evolved and proven their power. Currently we see an evolution from the distributed object access paradigm represented e.g. by middleware architectures like CORBA, DCOM or RMI towards Service Oriented Architectures (SOA), entailing a retrogression to the Client/Server paradigm. In this paper we want to present how Peer-To-Peer Applications can to a large extend benefit from intrinsic Web Service properties like loose coupling, declarative interface definition and interoperability, thus incorporating advantages from SOA and the Peer-To-Peer approach, opening new fields of application to both of them. For this purpose, WebFederate, a prototype middleware based on Microsoft’s.NET Framework has been implemented and will be presented in this paper.

Abstract

Dependability, lucidity of design and ease-of-administration are more and more outrivaling performance as the top priority in Operating System design. These endeavors have led to a new generation of Operating Systems that abolish physical address space separation by the restriction to type-safe languages and memory-managed runtime environments. Provided that adequately efficient XML-message representations are used, this paper argues that these novel approaches to OS design are well-suited to make XML-Message-based communication sufficiently fast to introduce it along with the notion of services into the very heart of Operating Systems. By these means a truly homogeneous communication scheme can be offered in which services provided by the Operating System, applications and remote entities can be consumed alike. This paper will present motivation and implementation of SISC, a SOAP-based and service-oriented middleware prototype facilitating shared DOM communication in next-generation Operating Systems. It also presents some preliminary performance measurements that suggest the viability of the underlying approach.

Abstract

The ATLAS Event Monitoring service (Emon) is a CORBA-based Peer-to-Peer data distribution framework, which has been implemented for CERN's forthcoming particle physics experiment ATLAS. Its purpose is to sample collision events from various stages of the data flow chain and efficiently distribute them to the users. Starting from a centralized predecessor version, this paper discusses various technical details of the current implementation along with a comparative study of communication complexity and scalability and a presentation of practical test results obtained during the HLT/DAQ large scale and performance test period in July 2005. Apart from that, a recent addition allowing users the parallel analysis of event data will be presented.

Abstract

This paper presents the idea of Web service interface syndication - a scheme for the collaborative creation of overlay networks based on common Web service interfaces. Rather than requiring complex management of dynamic peers we picture a setting of interconnected static Web applications forming syndicates and offering services in a self-organized fashion. Among other application scenarios, this paper will present vicinitySearch, a collaborative Weblog search service which has been created in order to demonstrate the concept. This service offers a remarkable added-value to the Weblog community, making use of existing collaborative structures and the interoperability provided by XML Web services. Apart from the general concept of Web service interface syndication, the paper presents an implementation of the vicinitySearch service that has been done in terms of a Wordpress plugin

Abstract

In this paper, mLearning extensions to CrePes, a programming environment tailored to the special needs of kids at age 8 and above are introduced. This software has been developed and used by our working groups for three years in order to leverage programming skills in secondary computer science classes at school. While it has been used successfully in the past, in this paper we present new applications and usage scenarios mobile devices open up for the CrePes environment

Abstract

This document presents the high-level design of the Event Monitoring framework within the ATLAS TDAQ system. The aim of the Event Monitoring component is to provide a framework in order to enable users to require samples of events or event fragments and distribute them to running monitoring tasks.

Abstract

The Atlas Event Monitoring system is a subsystem of the Atlas Online Software, providing a framework for sampling events from different stages of the data flow chain of the ATLAS detector and distributing it to so-called Monitoring Tasks run by physicists. After a short introduction to the ATLAS experiment, the data aquisition project and its different software components and the general purpose of Event Monitoring, this thesis discusses the previous implementation as well as different aspects of the reimplementation that has been done in the context of this thesis. After having done a theoretical analysis of the communication complexity of both implementations and the presentation of practical performance test results captured during the Large Scale Test period a conclusion will be made, showing why the reimplementation is more suitable for actual usage in the final experiment than the previous implementation.

Abstract

This document provides a detailed report on the first HLT/DAQ integrated Large Scale and Performance Tests which were performed in June/July 2005 on the CERN IT LXBATCH cluster. DAQ/HLT System Software tests as well as extended component tests were run on a PC farm size of up to 700 nodes. The integrated system under test included the Online Software, the DataFlow software, Level 2 trigger software and Event Filter software without algorithms. Tests including algorithms were successfully run independently for the Level 2 trigger and the Event Filter. Results are presented, compared to previous tests where applicable and suggestions for the further development and future tests are discussed.