MM
M. Märtens
info
Please Note
<p>This page displays the records of the person named above and is not linked to a unique person identifier. This record may need to be merged to a profile.</p>
8 records found
1
Information Propagation in Complex Networks
Structures and Dynamics
This thesis is a contribution to a deeper understanding of how information propagates and what this process entails. At its very core is the concept of the network: a collection of nodes and links, which describes the structure of the systems under investigation. The network is a mathematical model which allows to focus on a very fundamental property: the mutual relations (links) between information exchanging agents (nodes). This simplicity makes networks elegant, as no specifics of any supporting hardware are needed to reason on this high level of abstraction. The developing field of network science led to countless applications of the network model to all sorts of complex systems in nature and technology. Naturally, it became an essential part of many multi-disciplinary research projects. Therefore, understanding how information propagates in networks enables us to learn and conceivably control the intricate processes, which we observe in complex systems. Since complex systems are the driver for this research, the first three chapters of this thesis are studies based on data collected from vastly different application domains, after more fundamental research is addressed in the later parts.
Chapter 2 deals with the interaction of players of a popular multiplayer online game. Due to the competitive design of the game, teams are formed ad-hoc and compete with each other for victory. Some of the players exhibit anti-social behavior towards their teammates, which is known as toxicity. We analyze how toxicity in player networks emerges by developing a toxicity detector, highlighting possible triggers and analyze the disposition of players towards toxic teammates. Furthermore, we show how toxicity is linked to game success.
Chapter 3 continues with a study of the human brain as a functional network. Information processing in the brain is measurable with technologies like magnetoencephalography. From such measurements that were collected from a group of subjects, the phase transfer entropy is computed as a quantity that reflects information exchange. When associated with the links between brain regions, unusual high numbers of certain substructures are observed in this network. We find that one of these substructures, the bi-directional two-hop path, to be highly abundant and robust within different frequencies bands, which highlights its importance for the propagation of brain activity. A clustering of the network based on these frequent substructures reveals a spatially coherent organization of important brain regions.
A common symbol of propagation is the virus, which is at the center of the third data-driven analysis of this thesis in Chapter 4. More precisely, we research the digital version of the virus, the computer worm, and analyze its propagation by epidemic network models. With epidemic models, the state of the nodes in a network can be described as susceptible or infected. An infection process and a curing process determine how the nodes are changing between those states. We extend on the standard epidemic models, the SIS model, by a time-dependent curing rate function to reflect the changes in the effectiveness of the active worm removal. Once we set the curing rate function, the empirical worm data are fitted and analyzed on multiple scales from the global over the country down to the autonomous system level. The fitted model explains how computer worms or similar self-replicating pieces of information might change in their effectiveness over long periods of time.
The SIS model returns as a central piece in Chapter 5 again. Although spreading processes are frequently modeled in isolation, the dynamics of many real-world applications are often driven by the interaction of multiple of such processes. These interactions can range from viruses that compete for susceptible nodes to viruses that mutually reinforce their propagation. We study the special case of superinfection, in which one dominant virus spreads within the infected population of a weaker virus. We highlight the conditions for which a co-existence of both viruses is stable and show that extinction cycles become possible if the infection rate of the dominant virus becomes too strong. Furthermore, we show that some of the possible outcomes of a superinfection are difficult to approximate with common mean-field techniques. However, the second largest eigenvalue of the infinitesimal generator of the underlying Markov process is potentially linked to co-existence and thus stability.
Chapter 6 is a study on the capabilities of symbolic regression for network properties. We develop an automated system based on Genetic Programming which is able to be trained by families of networks to learn the relations between several of their properties. These properties can be features of the networks like the eigenvalues of their adjacency or Laplacian matrices or network metrics like the network diameter or the isoperimetric number. We show that the system can generate approximate formulas for those metrics that often give better results than previously known analytic bounds. The evolved formulas for the network diameter are evaluated on a selection of real-world networks of different origins. The network diameter bounds hop-based information propagation and is thus of high importance for designing network algorithms. A careful selection of training networks and network features is crucial for evolving good approximate formulas for the network diameter and similar properties.
Finally, the thesis concludes with Chapter 7 which revisits the concepts that were developed and provides some critical assessment on their potential and limitations.
...
This thesis is a contribution to a deeper understanding of how information propagates and what this process entails. At its very core is the concept of the network: a collection of nodes and links, which describes the structure of the systems under investigation. The network is a mathematical model which allows to focus on a very fundamental property: the mutual relations (links) between information exchanging agents (nodes). This simplicity makes networks elegant, as no specifics of any supporting hardware are needed to reason on this high level of abstraction. The developing field of network science led to countless applications of the network model to all sorts of complex systems in nature and technology. Naturally, it became an essential part of many multi-disciplinary research projects. Therefore, understanding how information propagates in networks enables us to learn and conceivably control the intricate processes, which we observe in complex systems. Since complex systems are the driver for this research, the first three chapters of this thesis are studies based on data collected from vastly different application domains, after more fundamental research is addressed in the later parts.
Chapter 2 deals with the interaction of players of a popular multiplayer online game. Due to the competitive design of the game, teams are formed ad-hoc and compete with each other for victory. Some of the players exhibit anti-social behavior towards their teammates, which is known as toxicity. We analyze how toxicity in player networks emerges by developing a toxicity detector, highlighting possible triggers and analyze the disposition of players towards toxic teammates. Furthermore, we show how toxicity is linked to game success.
Chapter 3 continues with a study of the human brain as a functional network. Information processing in the brain is measurable with technologies like magnetoencephalography. From such measurements that were collected from a group of subjects, the phase transfer entropy is computed as a quantity that reflects information exchange. When associated with the links between brain regions, unusual high numbers of certain substructures are observed in this network. We find that one of these substructures, the bi-directional two-hop path, to be highly abundant and robust within different frequencies bands, which highlights its importance for the propagation of brain activity. A clustering of the network based on these frequent substructures reveals a spatially coherent organization of important brain regions.
A common symbol of propagation is the virus, which is at the center of the third data-driven analysis of this thesis in Chapter 4. More precisely, we research the digital version of the virus, the computer worm, and analyze its propagation by epidemic network models. With epidemic models, the state of the nodes in a network can be described as susceptible or infected. An infection process and a curing process determine how the nodes are changing between those states. We extend on the standard epidemic models, the SIS model, by a time-dependent curing rate function to reflect the changes in the effectiveness of the active worm removal. Once we set the curing rate function, the empirical worm data are fitted and analyzed on multiple scales from the global over the country down to the autonomous system level. The fitted model explains how computer worms or similar self-replicating pieces of information might change in their effectiveness over long periods of time.
The SIS model returns as a central piece in Chapter 5 again. Although spreading processes are frequently modeled in isolation, the dynamics of many real-world applications are often driven by the interaction of multiple of such processes. These interactions can range from viruses that compete for susceptible nodes to viruses that mutually reinforce their propagation. We study the special case of superinfection, in which one dominant virus spreads within the infected population of a weaker virus. We highlight the conditions for which a co-existence of both viruses is stable and show that extinction cycles become possible if the infection rate of the dominant virus becomes too strong. Furthermore, we show that some of the possible outcomes of a superinfection are difficult to approximate with common mean-field techniques. However, the second largest eigenvalue of the infinitesimal generator of the underlying Markov process is potentially linked to co-existence and thus stability.
Chapter 6 is a study on the capabilities of symbolic regression for network properties. We develop an automated system based on Genetic Programming which is able to be trained by families of networks to learn the relations between several of their properties. These properties can be features of the networks like the eigenvalues of their adjacency or Laplacian matrices or network metrics like the network diameter or the isoperimetric number. We show that the system can generate approximate formulas for those metrics that often give better results than previously known analytic bounds. The evolved formulas for the network diameter are evaluated on a selection of real-world networks of different origins. The network diameter bounds hop-based information propagation and is thus of high importance for designing network algorithms. A careful selection of training networks and network features is crucial for evolving good approximate formulas for the network diameter and similar properties.
Finally, the thesis concludes with Chapter 7 which revisits the concepts that were developed and provides some critical assessment on their potential and limitations.
Within the vast and rich field of online gaming, a new generation of Online Social Games (OSGs) is emerging that have in common a core of social interaction, sometimes explicit, other times implicit. This common core of social experience promises to become at least as important as the experience derived from the game-‐world itself. In this chapter, we consider the social side of OSGs and provide the following contributions: 1.We motivate the importance of taking social features into account to improve the quality of experience in online gaming. 2.We discuss the various dimensions of (player experience in) OSGs.
3.We describe a social network analysis methodology for identifying relations in OSGs and indicate how this methodology could be used to improve the game-‐play experience. 4.We also consider and illustrate how certain “social” behaviour, like toxicity, is negative and may harm the game-‐play experience, if not adequately addressed. 5.We mention several directions for future research to put the power of social features in OSGs to good use.
...
Within the vast and rich field of online gaming, a new generation of Online Social Games (OSGs) is emerging that have in common a core of social interaction, sometimes explicit, other times implicit. This common core of social experience promises to become at least as important as the experience derived from the game-‐world itself. In this chapter, we consider the social side of OSGs and provide the following contributions: 1.We motivate the importance of taking social features into account to improve the quality of experience in online gaming. 2.We discuss the various dimensions of (player experience in) OSGs.
3.We describe a social network analysis methodology for identifying relations in OSGs and indicate how this methodology could be used to improve the game-‐play experience. 4.We also consider and illustrate how certain “social” behaviour, like toxicity, is negative and may harm the game-‐play experience, if not adequately addressed. 5.We mention several directions for future research to put the power of social features in OSGs to good use.
Network science has widely studied the properties of brain networks. Recent work has observed a global back-to-front pattern of information flow for higher frequency bands in magnetoencephalography data. However, the effective connectivity at a local level remains yet to be analyzed. On a local level, the building blocks of all networks are motifs. In this study, we exploit the measure of dPTE to analyze motifs of the estimated effective connectivity networks. We find that some 3- and 4-motifs, the bidirectional two-hop path and its extended 4-node versions, are significantly overexpressed in the analyzed networks in comparison with random networks. With a recently developed motif-based clustering algorithm we separate the effective connectivity network in two main clusters which reveal its higher-order organization with a strong information flow between posterior hubs and anterior regions.
...
Network science has widely studied the properties of brain networks. Recent work has observed a global back-to-front pattern of information flow for higher frequency bands in magnetoencephalography data. However, the effective connectivity at a local level remains yet to be analyzed. On a local level, the building blocks of all networks are motifs. In this study, we exploit the measure of dPTE to analyze motifs of the estimated effective connectivity networks. We find that some 3- and 4-motifs, the bidirectional two-hop path and its extended 4-node versions, are significantly overexpressed in the analyzed networks in comparison with random networks. With a recently developed motif-based clustering algorithm we separate the effective connectivity network in two main clusters which reveal its higher-order organization with a strong information flow between posterior hubs and anterior regions.
Networks are continuously growing in complexity, which creates challenges for determining their most important characteristics. While analytical bounds are often too conservative, the computational effort of algorithmic approaches does not scale well with network size. This work uses Cartesian Genetic Programming for symbolic regression to evolve mathematical equations that relate network properties directly to the eigenvalues of network adjacency and Laplacian matrices. In particular, we show that these eigenvalues are powerful features to evolve approximate equations for the network diameter and the isoperimetric number, which are hard to compute algorithmically. Our experiments indicate a good performance of the evolved equations for several real-world networks and we demonstrate how the generalization power can be influenced by the selection of training networks and feature sets.
...
Networks are continuously growing in complexity, which creates challenges for determining their most important characteristics. While analytical bounds are often too conservative, the computational effort of algorithmic approaches does not scale well with network size. This work uses Cartesian Genetic Programming for symbolic regression to evolve mathematical equations that relate network properties directly to the eigenvalues of network adjacency and Laplacian matrices. In particular, we show that these eigenvalues are powerful features to evolve approximate equations for the network diameter and the isoperimetric number, which are hard to compute algorithmically. Our experiments indicate a good performance of the evolved equations for several real-world networks and we demonstrate how the generalization power can be influenced by the selection of training networks and feature sets.
Journal article
(2017)
-
Marcus Märtens, Jil Meier, Arjan Hillebrand, Prejaas Tewarie, Piet Van Mieghem
Recent work has revealed frequency-dependent global patterns of information flow by a network analysis of magnetoencephalography data of the human brain. However, it is unknown which properties on a small subgraph-scale of those functional brain networks are dominant at different frequencies bands. Motifs are the building blocks of networks on this level and have previously been identified as important features for healthy and abnormal brain function. In this study, we present a network construction that enables us to search and analyze motifs in different frequency bands. We give evidence that the bi-directional two-hop path is the most important motif for the information flow in functional brain networks. A clustering based on this motif exposes a spatially coherent yet frequency-dependent sub-division between the posterior, occipital and frontal brain regions.
...
Recent work has revealed frequency-dependent global patterns of information flow by a network analysis of magnetoencephalography data of the human brain. However, it is unknown which properties on a small subgraph-scale of those functional brain networks are dominant at different frequencies bands. Motifs are the building blocks of networks on this level and have previously been identified as important features for healthy and abnormal brain function. In this study, we present a network construction that enables us to search and analyze motifs in different frequency bands. We give evidence that the bi-directional two-hop path is the most important motif for the information flow in functional brain networks. A clustering based on this motif exposes a spatially coherent yet frequency-dependent sub-division between the posterior, occipital and frontal brain regions.
Epidemic models like the SIS or SIR model enable us to describe simple spreading processes over networks but are often not sufficient to accurately capture more complex network dynamics as exhibited by sophisticated and malicious computer worms. Many of the common assumptions behind epidemic models do not necessary hold if the process under investigation spans big networks or large scales of time.We extend the standard SIS network model by dropping the assumption of a constant curing rate in favour of a time-dependent curing rate function, which enables us to reflect changes in the effectiveness of the active worm removal process over time. The resulting time-dependent mean-field SIS model allows us to study the evolution of the size of computer worm bot-nets. We exemplify the complete procedure, including data-processing, needed to obtain a reliable model on data from Conficker, an extremely resilient computer worm. Using empirical data obtained from the Conficker sinkhole, we fit long time periods of up to 6 years on multiple scales and different levels of noise. We end by reflecting on the limits of epidemic models in empirical analysis of malware threats.
...
Epidemic models like the SIS or SIR model enable us to describe simple spreading processes over networks but are often not sufficient to accurately capture more complex network dynamics as exhibited by sophisticated and malicious computer worms. Many of the common assumptions behind epidemic models do not necessary hold if the process under investigation spans big networks or large scales of time.We extend the standard SIS network model by dropping the assumption of a constant curing rate in favour of a time-dependent curing rate function, which enables us to reflect changes in the effectiveness of the active worm removal process over time. The resulting time-dependent mean-field SIS model allows us to study the evolution of the size of computer worm bot-nets. We exemplify the complete procedure, including data-processing, needed to obtain a reliable model on data from Conficker, an extremely resilient computer worm. Using empirical data obtained from the Conficker sinkhole, we fit long time periods of up to 6 years on multiple scales and different levels of noise. We end by reflecting on the limits of epidemic models in empirical analysis of malware threats.
Social interactions in multiplayer online games are an essential feature for a growing number of players world-wide. However, this interaction between the players might lead to the emergence of undesired and unintended behavior, particularly if the game is designed to be highly competitive. Communication channels might be abused to harass and verbally assault other players, which negates the very purpose of entertainment games by creating a toxic player-community. By using a novel natural language processing framework, we detect profanity in chat-logs of a popular Multiplayer Online Battle Arena (MOBA) game and develop a method to classify toxic remarks. We show how toxicity is non-trivially linked to game success.
...
Social interactions in multiplayer online games are an essential feature for a growing number of players world-wide. However, this interaction between the players might lead to the emergence of undesired and unintended behavior, particularly if the game is designed to be highly competitive. Communication channels might be abused to harass and verbally assault other players, which negates the very purpose of entertainment games by creating a toxic player-community. By using a novel natural language processing framework, we detect profanity in chat-logs of a popular Multiplayer Online Battle Arena (MOBA) game and develop a method to classify toxic remarks. We show how toxicity is non-trivially linked to game success.