-
Community detection and anomaly prediction in dynamic networks
Authors:
Hadiseh Safdari,
Caterina De Bacco
Abstract:
Anomaly detection is an essential task in the analysis of dynamic networks, as it can provide early warning of potential threats or abnormal behavior. We present a principled approach to detect anomalies in dynamic networks that integrates community structure as a foundational model for regular behavior. Our model identifies anomalies as irregular edges while capturing structural changes. Leveragi…
▽ More
Anomaly detection is an essential task in the analysis of dynamic networks, as it can provide early warning of potential threats or abnormal behavior. We present a principled approach to detect anomalies in dynamic networks that integrates community structure as a foundational model for regular behavior. Our model identifies anomalies as irregular edges while capturing structural changes. Leveraging a Markovian approach for temporal transitions and incorporating structural information via latent variables for communities and anomaly detection, our model infers these hidden parameters to pinpoint abnormal interactions within the network. Our approach is evaluated on both synthetic and real-world datasets. Real-world network analysis shows strong anomaly detection across diverse scenarios. In a more specific study of transfers of professional male football players, we observe various types of unexpected patterns and investigate how the country and wealth of clubs influence interactions. Additionally, we identify anomalies between clubs with incompatible community memberships, but also instances of anomalous transactions between clubs with similar memberships. The latter is due in particular to the dynamic nature of the transactions, as we find that the frequency of transfers results in anomalous behaviors that are otherwise expected to interact as they belong to similar communities.
△ Less
Submitted 16 April, 2024;
originally announced April 2024.
-
Anomaly, reciprocity, and community detection in networks
Authors:
Hadiseh Safdari,
Martina Contisciani,
Caterina De Bacco
Abstract:
Anomaly detection algorithms are a valuable tool in network science for identifying unusual patterns in a network. These algorithms have numerous practical applications, including detecting fraud, identifying network security threats, and uncovering significant interactions within a dataset. In this project, we propose a probabilistic generative approach that incorporates community membership and…
▽ More
Anomaly detection algorithms are a valuable tool in network science for identifying unusual patterns in a network. These algorithms have numerous practical applications, including detecting fraud, identifying network security threats, and uncovering significant interactions within a dataset. In this project, we propose a probabilistic generative approach that incorporates community membership and reciprocity as key factors driving regular behavior in a network, which can be used to identify potential anomalies that deviate from expected patterns. We model pairs of edges in a network with exact two-edge joint distributions. As a result, our approach captures the exact relationship between pairs of edges and provides a more comprehensive view of social networks. Additionally, our study highlights the role of reciprocity in network analysis and can inform the design of future models and algorithms. We also develop an efficient algorithmic implementation that takes advantage of the sparsity of the network.
△ Less
Submitted 1 February, 2023;
originally announced February 2023.
-
Anomaly detection and community detection in networks
Authors:
Hadiseh Safdari,
Caterina De Bacco
Abstract:
Anomaly detection is a relevant problem in the area of data analysis. In networked systems, where individual entities interact in pairs, anomalies are observed when pattern of interactions deviates from patterns considered regular. Properly defining what regular patterns entail relies on developing expressive models for describing the observed interactions. It is crucial to address anomaly detecti…
▽ More
Anomaly detection is a relevant problem in the area of data analysis. In networked systems, where individual entities interact in pairs, anomalies are observed when pattern of interactions deviates from patterns considered regular. Properly defining what regular patterns entail relies on developing expressive models for describing the observed interactions. It is crucial to address anomaly detection in networks. Among the many well-known models for networks, latent variable models - a class of probabilistic models - offer promising tools to capture the intrinsic features of the data. In this work, we propose a probabilistic generative approach that incorporates domain knowledge, i.e., community membership, as a fundamental model for regular behavior, and thus flags potential anomalies deviating from this pattern. In fact, community membership serves as the building block of a null model to identify the regular interaction patterns. The structural information is included in the model through latent variables for community membership and anomaly parameter. The algorithm aims at inferring these latent parameters and then output the labels identifying anomalies on the network edges.
△ Less
Submitted 19 August, 2022; v1 submitted 12 May, 2022;
originally announced May 2022.
-
Latent Network Models to Account for Noisy, Multiply-Reported Social Network Data
Authors:
Caterina De Bacco,
Martina Contisciani,
Jonathan Cardoso-Silva,
Hadiseh Safdari,
Diego Baptista,
Gabriela L. Borges,
Tracy Sweet,
Jean-Gabriel Young,
Jeremy Koster,
Cody T. Ross,
Richard McElreath,
Daniel Redhead,
Eleanor A. Power
Abstract:
Social network data are often constructed by incorporating reports from multiple individuals. However, it is not obvious how to reconcile discordant responses from individuals. There may be particular risks with multiply-reported data if people's responses reflect normative expectations -- such as an expectation of balanced, reciprocal relationships. Here, we propose a probabilistic model that inc…
▽ More
Social network data are often constructed by incorporating reports from multiple individuals. However, it is not obvious how to reconcile discordant responses from individuals. There may be particular risks with multiply-reported data if people's responses reflect normative expectations -- such as an expectation of balanced, reciprocal relationships. Here, we propose a probabilistic model that incorporates ties reported by multiple individuals to estimate the unobserved network structure. In addition to estimating a parameter for each reporter that is related to their tendency of over- or under-reporting relationships, the model explicitly incorporates a term for ``mutuality,'' the tendency to report ties in both directions involving the same alter. Our model's algorithmic implementation is based on variational inference, which makes it efficient and scalable to large systems. We apply our model to data from 75 Indian villages collected with a name-generator design, and a Nicaraguan community collected with a roster-based design. We observe strong evidence of ``mutuality'' in both datasets, and find that this value varies by relationship type. Consequently, our model estimates networks with reciprocity values that are substantially different than those resulting from standard deterministic aggregation approaches, demonstrating the need to consider such issues when gathering, constructing, and analysing survey-based network data.
△ Less
Submitted 12 December, 2022; v1 submitted 21 December, 2021;
originally announced December 2021.
-
Community detection and reciprocity in networks by jointly modeling pairs of edges
Authors:
Martina Contisciani,
Hadiseh Safdari,
Caterina De Bacco
Abstract:
To unravel the driving patterns of networks, the most popular models rely on community detection algorithms. However, these approaches are generally unable to reproduce the structural features of the network. Therefore, attempts are always made to develop models that incorporate these network properties beside the community structure. In this work, we present a probabilistic generative model and a…
▽ More
To unravel the driving patterns of networks, the most popular models rely on community detection algorithms. However, these approaches are generally unable to reproduce the structural features of the network. Therefore, attempts are always made to develop models that incorporate these network properties beside the community structure. In this work, we present a probabilistic generative model and an efficient algorithm to both perform community detection and capture reciprocity in networks. Our approach jointly models pairs of edges with exact 2-edge joint distributions. In addition, it provides closed-form analytical expressions for both marginal and conditional distributions. We validate our model on synthetic data in recovering communities, edge prediction tasks, and generating synthetic networks that replicate the reciprocity values observed in real networks. We also highlight these findings on two real datasets that are relevant for social scientists and behavioral ecologists. Our method overcomes the limitations of both standard algorithms and recent models that incorporate reciprocity through a pseudo-likelihood approximation. The inference of the model parameters is implemented by the efficient and scalable expectation-maximization algorithm, as it exploits the sparsity of the dataset. We provide an open-source implementation of the code online.
△ Less
Submitted 6 September, 2022; v1 submitted 20 December, 2021;
originally announced December 2021.
-
Reciprocity, community detection, and link prediction in dynamic networks
Authors:
Hadiseh Safdari,
Martina Contisciani,
Caterina De Bacco
Abstract:
Many complex systems change their structure over time, in these cases dynamic networks can provide a richer representation of such phenomena. As a consequence, many inference methods have been generalized to the dynamic case with the aim to model dynamic interactions. Particular interest has been devoted to extend the stochastic block model and its variant, to capture community structure as the ne…
▽ More
Many complex systems change their structure over time, in these cases dynamic networks can provide a richer representation of such phenomena. As a consequence, many inference methods have been generalized to the dynamic case with the aim to model dynamic interactions. Particular interest has been devoted to extend the stochastic block model and its variant, to capture community structure as the network changes in time. While these models assume that edge formation depends only on the community memberships, recent work for static networks show the importance to include additional parameters capturing structural properties, as reciprocity for instance. Remarkably, these models are capable of generating more realistic network representations than those that only consider community membership. To this aim, we present a probabilistic generative model with hidden variables that integrates reciprocity and communities as structural information of networks that evolve in time. The model assumes a fundamental order in observing reciprocal data, that is an edge is observed, conditional on its reciprocated edge in the past. We deploy a Markovian approach to construct the network's transition matrix between time steps and parameters' inference is performed with an Expectation-Maximization algorithm that leads to high computational efficiency because it exploits the sparsity of the dataset. We test the performance of the model on synthetic dynamical networks, as well as on real networks of citations and email datasets. We show that our model captures the reciprocity of real networks better than standard models with only community structure, while performing well at link prediction tasks.
△ Less
Submitted 17 December, 2021;
originally announced December 2021.
-
Generative model for reciprocity and community detection in networks
Authors:
Hadiseh Safdari,
Martina Contisciani,
Caterina De Bacco
Abstract:
We present a probabilistic generative model and efficient algorithm to model reciprocity in directed networks. Unlike other methods that address this problem such as exponential random graphs, it assigns latent variables as community memberships to nodes and a reciprocity parameter to the whole network rather than fitting order statistics. It formalizes the assumption that a directed interaction i…
▽ More
We present a probabilistic generative model and efficient algorithm to model reciprocity in directed networks. Unlike other methods that address this problem such as exponential random graphs, it assigns latent variables as community memberships to nodes and a reciprocity parameter to the whole network rather than fitting order statistics. It formalizes the assumption that a directed interaction is more likely to occur if an individual has already observed an interaction towards her. It provides a natural framework for relaxing the common assumption in network generative models of conditional independence between edges, and it can be used to perform inference tasks such as predicting the existence of an edge given the observation of an edge in the reverse direction. Inference is performed using an efficient expectation-maximization algorithm that exploits the sparsity of the network, leading to an efficient and scalable implementation. We illustrate these findings by analyzing synthetic and real data, including social networks, academic citations and the Erasmus student exchange program. Our method outperforms others in both predicting edges and generating networks that reflect the reciprocity values observed in real data, while at the same time inferring an underlying community structure. We provide an open-source implementation of the code online.
△ Less
Submitted 6 September, 2022; v1 submitted 15 December, 2020;
originally announced December 2020.
-
Fractional Dynamics of Network Growth Constrained by aging Node Interactions
Authors:
Hadiseh Safdari,
Milad Zare Kamali,
Amirhossein Shirazi,
Moein Khalighi,
Gholamreza Jafari,
Marcel Ausloos
Abstract:
In many social complex systems, in which agents are linked by non-linear interactions, the history of events strongly influences the whole network dynamics. However, a class of "commonly accepted beliefs" seems rarely studied. In this paper, we examine how the growth process of a (social) network is influenced by past circumstances. In order to tackle this cause, we simply modify the well known pr…
▽ More
In many social complex systems, in which agents are linked by non-linear interactions, the history of events strongly influences the whole network dynamics. However, a class of "commonly accepted beliefs" seems rarely studied. In this paper, we examine how the growth process of a (social) network is influenced by past circumstances. In order to tackle this cause, we simply modify the well known preferential attachment mechanism by imposing a time dependent kernel function in the network evolution equation. This approach leads to a fractional order Barabasi-Albert (BA) differential equation, generalizing the BA model. Our results show that, with passing time, an aging process is observed for the network dynamics. The aging process leads to a decay for the node degree values, thereby creating an opposing process to the preferential attachment mechanism. On one hand, based on the preferential attachment mechanism, nodes with a high degree are more likely to absorb links; but, on the other hand, a node's age has a reduced chance for new connections. This competitive scenario allows an increased chance for younger members to become a hub. Simulations of such a network growth with aging constraint confirm the results found from solving the fractional BA equation. We also report, as an exemplary application, an investigation of the collaboration network between Hollywood movie actors. It is undubiously shown that a decay in the dynamics of their collaboration rate is found, - even including a sex difference. Such findings suggest a widely universal application of the so generalized BA model.
△ Less
Submitted 9 September, 2017;
originally announced September 2017.
-
Glassy states of aging social networks
Authors:
F. Hassanibesheli,
L. Hedayatifar,
H. Safdari,
M. Ausloos,
G. R. Jafari
Abstract:
Individuals often develop reluctance to change their social relations, called "secondary homebody", even though their interactions with their environment evolve with time. Some memory effect is loosely present deforcing changes. In other words, in presence of memory, relations do not change easily. In order to investigate some history or memory effect on social networks, we introduce a temporal ke…
▽ More
Individuals often develop reluctance to change their social relations, called "secondary homebody", even though their interactions with their environment evolve with time. Some memory effect is loosely present deforcing changes. In other words, in presence of memory, relations do not change easily. In order to investigate some history or memory effect on social networks, we introduce a temporal kernel function into the Heider conventional balance theory, allowing for the "quality" of past relations to contribute to the evolution of the system. This memory effect is shown to lead to the emergence of aged networks, thereby perfectly describing and the more so measuring the aging process of links ("social relations"). It is shown that such a memory does not change the dynamical attractors of the system, but does prolong the time necessary to reach the "balanced states". The general trend goes toward obtaining either global ("paradise" or "bipolar") or local ("jammed") balanced states, but is profoundly affected by aged relations. The resistance of elder links against changes decelerates the evolution of the system and traps it into so named glassy states. In contrast to balance
△ Less
Submitted 9 September, 2017;
originally announced September 2017.
-
History effects on network growth
Authors:
Hadiseh Safdari,
Milad Zare Kamali,
Amir Hossein Shirazi,
Moein Khaliqi,
Gholamreza Jafari
Abstract:
Growth dynamic of real networks because of emerging complexities is an open and interesting question. Indeed it is not realistic to ignore history impact on the current events. The mystery behind that complexity could be in the role of history in some how. To regard this point, the average effect of history has been included by a kernel function in differential equation of Barabasi Albert (BA) mod…
▽ More
Growth dynamic of real networks because of emerging complexities is an open and interesting question. Indeed it is not realistic to ignore history impact on the current events. The mystery behind that complexity could be in the role of history in some how. To regard this point, the average effect of history has been included by a kernel function in differential equation of Barabasi Albert (BA) model . This approach leads to a fractional order BA differential equation as a generalization of BA model. As opposed to unlimited growth for degree of nodes, our results show that over time the memory impact will cause a decay for degrees. This gives a higher chance to younger members for turning to a hub. In fact in a real network, there are two competitive processes. On one hand, based on preferential attachment mechanism nodes with higher degree are more likely to absorb links. On the other hand, node history through aging process prevents new connections. Our findings from simulating a network grown by considering these effects also from studying a real network of collaboration between Hollywood movie actors conforms the results and significant effects of history and time on dynamic.
△ Less
Submitted 24 May, 2015;
originally announced May 2015.
