Algorithmic decisions on network-structured data, such as community detection, often remain opaque, leaving individuals without agency over how they are categorized. This article introduces a general framework for algorithmic recourse on networks, designed to provide actionable recommendations for nodes seeking to alter their assigned properties. Shifting the focus from descriptive interpretability “Why?” to prescriptive actionability “How?”, we formulate recourse as a nearest-counterfactual search constrained by an actionable set, which is a subset of edges a user has the power to modify. We introduce a weight-aware notion of responsibility that functions as a feasibility metric, quantifying the minimal cost of interventions required to achieve a desired outcome. To demonstrate the framework’s broad applicability, we apply it to the community detection problem, where the goal is to identify the most feasible edge modifications that allow a node to leave a specific community. We provide a theoretical treatise for a modification method that enables an efficient search procedure with provable approximation guarantees. Our experiments on a diverse suite of real-world networks demonstrate that our method achieves high success rates with low-cost interventions in both weighted and unweighted scenarios. Furthermore, comparisons with a state-of-the-art Deep Reinforcement Learning Agent reveal that our interpretable framework matches or exceeds, in most cases, the performance of complex black-box methods. The primary contribution of this work is an interpretable and tenable framework for network recourse, emphasizing that transparent, structural manipulation is a robust alternative to complex learning-based approaches for restoring user agency.

This paper presents a comprehensive framework for understanding the properties of nodes in a weighted network related to an algorithmic process based on counterfactuals.The framework is applied to the problem of community detection to demonstrate its general applicability.It identifies counterfactual explanations, revealing which network connections, when modified by changing their weights, would cause a node to lose its community affiliation, answering questions like "Why does node v belong to community C?".The core contribution lies in providing an interpretable and actionable framework for understanding and manipulating network structures. Index Terms-networks, counterfactual explanations, community detection• Assume for the network G = (V, E, w) it holds that v ∈ P. If for G ′ = (V, E, w ′ ), where only w e is changed

Community detection stands as a pivotal process in network analysis, having undergone extensive examination over the past 25 years within static network contexts.This task involves partitioning networks based on structural characteristics, specifically into classes of nodes exhibiting denser connections than the overall network.Moreover, in recent years, an additional layer of complexity has arisen, particularly in networks characterized by a static nature where each node and edge is assigned a valid time interval.Such historical graphs, unlike traditional graphs, incorporate a temporal dimension, allowing for the analysis of how connections between entities evolve and change over different time intervals.In this study, we present a distributed algorithm for static community detection within a query time interval in historical graphs.Specifically, when provided with a designated query time interval, our proposed method identifies communities by assessing the individual contributions of each edge and node within the graph during that specified time interval.To the best of our knowledge, this setting has not been considered before in the literature.

Abstract Detecting pattern matches underpins key operations across fields, such as complex event processing (CEP), sequential pattern mining (SPM), string pattern matching, pattern mining from a large sequence, and business process mining. These fields employ various notations and definitions for the detected patterns, posing challenges in recognizing their shared underlying concepts. This work aims to bridge these gaps by proposing a unified notation and terminology and then cataloging various pattern queries and constraints identified in different fields into a comprehensive framework. Our analysis reveals substantial similarities among the various pattern types, suggesting a promising avenue for the transfer of techniques between disciplines. This approach paves the way to leverage existing knowledge efficiently and circumvent the redundancy of “reinventing the wheel”.

We deal with the efficient implementation of storage models for time-varying graphs. To this end, we present an improved approach for the HiNode vertex-centric model based on MongoDB. This approach, apart from its inherent space optimality, exhibits significant improvements in global query execution times, which is the most challenging query type for entity-centric approaches. Not only significant speedups are achieved but more expensive queries can be executed as well, when compared to an implementation based on Cassandra due to the capability to exploit indices to a larger extent and benefit from in-database query processing.

We consider the general problem of the Longest Common Subsequence (LCS) on weighted sequences. Weighted sequences are an extension of classical strings, where in each position every letter of the alphabet may occur with some probability. Previous results presented a PTAS and noticed that no FPTAS is possible unless P=NP. In this paper we essentially close the gap between upper and lower bounds by improving both. First of all, we provide an EPTAS for bounded alphabets (which is the most natural case), and prove that there does not exist any EPTAS for unbounded alphabets unless FPT=W[1]. Furthermore, under the Exponential Time Hypothesis, we provide a lower bound which shows that no significantly better PTAS can exist for unbounded alphabets. As a side note, we prove that it is sufficient to work with only one threshold in the general variant of the problem.

In this work, we focus on distance-based outliers in a metric space, where the status of an entity as to whether it is an outlier is based on the number of other entities in its neighborhood. In the recent years, several solutions have tackled the problem of distance-based outliers in data streams, where outliers must be mined continuously as new elements become available. An interesting research problem is to combine the streaming environment with massively parallel systems to provide scalable stream-based algorithms. However, none of the previously proposed techniques refer to a massively parallel setting. Our proposal fills this gap and studies transferring state-of-the-art techniques in Apache Flink, a modern platform for intensive streaming analytics. We thoroughly present the technical challenges encountered and the alternatives that may be applied. We show speed-ups up to 117 (resp. 2076) times over a naive parallel (resp. non-parallel) solution in Flink, by using just an ordinary 4-core machine and a real-world dataset. Our results demonstrate that oulier mining can be achieved in an efficient and scalable manner. The resulting techniques have been made publicly available in open-source.

Suppose we have a virus or one competing idea/product that propagates over a multiple profile (e.g., social) network. Can we predict what proportion of the network will actually get "infected" (e.g., spread the idea or buy the competing product), when the nodes of the network appear to have different sensitivity based on their profile? For example, if there are two profiles A and B in a network and the nodes of profile A and profile B are susceptible to a highly spreading virus with probabilities βA and βB respectively, what percentage of both profiles will actually get infected from the virus at the end? To reverse the question, what are the necessary conditions so that a predefined percentage of the network is infected? We assume that nodes of different profiles can infect one another and we prove that under realistic conditions, apart from the weak profile (great sensitivity), the stronger profile (low sensitivity) will get infected as well. First, we focus on cliques with the goal to provide exact theoretical results as well as to get some intuition as to how a virus affects such a multiple profile network. Then, we move to the theoretical analysis of arbitrary networks. We provide bounds on certain properties of the network based on the probabilities of infection of each node in it when it reaches the steady state. Finally, we provide extensive experimental results that verify our theoretical results and at the same time provide more insight on the problem.

The top-k dominating query returns the k database objects with the highest score with respect to their dominance score. The dominance score of an object p is simply the number of objects dominated by p, based on minimization or max-imization preferences on the attribute values. Each object (tuple) is represented as a point in a multidimensional space, and therefore, the number of attributes equals the number of dimensions. The top-k dominating query combines the dominance concept of skyline queries with the ranking func-tion of top-k queries and can be used as an important tool in multi-criteria decision making systems. In this work, we focus on the 2-dimensional space and present, for the first time, novel algorithms for top-k dominating query process-ing in main memory with non-trivial asymptotic guarantees.

Dynamic recordings of functional activity maps can naturally and efficiently be represented in the form of functional/effective connectivity networks. New methods for mapping synaptic connections and recording neural signals generate rich and complex data about the structure and dynamics of brain networks. To study the most complex network in nature, the brain, there is need to integrate a huge amount of brain networks collected from laboratories over the world in large databases. Human Brain Project (Europe and USA) aims to explore brain functionality in various ways. Brain networks are central to achieving the goals of this ambitious plan. However, the immense amount of thousands of brain networks, prevent an easy way to utilizable knowledge. In this paper, we demonstrate a data-driven approach that discovers consistent patterns from a collection of brain networks via a querying approach: formulating a query of “finding an increasing or a decreasing consistent subgraph over an amount of subjects” after taking the difference between two sets of graphs referred as two conditions (an active and a baseline). Experiments demonstrated that our data-driven approach allows identifying frequency-dependent selective spatial pattern changes of the EEG functional connectivity network during a mental task. This is the first time that a method fully exploits the connectivity weights of a brain network to discover consistent subgraph patterns.

We study the static and dynamic planar range skyline reporting problem in the external memory model with block size B, under a linear space budget. The problem asks for an O(n/B) space data structure that stores n points in the plane, and supports reporting the k maximal input points (a.k.a.skyline) among the points that lie within a given query rectangle Q = [α1[α2] × [β1β2. When Q is 3-sided, i.e. one of its edges is grounded, two variants arise: top-open for β2 = ∞ and left-open for α1 = - ∞ (symmetrically bottom-open and right-open) queries.

Anomaly detection is an important data mining task, aiming at the discovery of elements that show significant diversion from the expected behavior; such elements are termed as outliers. One of the most widely employed criteria for determining whether an element is an outlier is based on the number of neighboring elements within a fixed distance (R), against a fixed threshold (k). Such outliers are referred to as distance-based outliers and are the focus of this work. In this demo, we show both an extendible framework for outlier detection algorithms and specific outlier detection algorithms for the demanding case where outlier detection is continuously performed over a data stream. More specifically: i) first we demonstrate a novel flavor of an open-source publicly available tool for Massive Online Analysis (MOA) that is endowed with capabilities to encapsulate algorithms that continuously detect outliers and ii) second, we present four online outlier detection algorithms. Two of these algorithms have been designed by the authors of this demo, with a view to improving on key aspects related to outlier mining, such as running time, flexibility and space requirements.

We present I/O-efficient fully persistent B-Trees that support range searches at any version in O(logB n + t/B) I/Os and updates at any version in O(logB n + log2 B) amortized I/Os, using space O(m/B) disk blocks. By n we denote the number of elements in the accessed version, by m the total number of updates, by t the size of the query's output, and by B the disk block size. The result improves the previous fully persistent B-Trees of Lanka and Mays by a factor of O(logB m) for the range query complexity and O(logB n) for the update complexity. To achieve the result, we first present a new B-Tree implementation that supports searches and updates in O(logB n) I/Os, using O(n/B) blocks of space. Moreover, every update makes in the worst case a constant number of modifications to the data structure. We make these B-Trees fully persistent using an I/O-efficient method for full persistence that is inspired by the node-splitting method of Driscoll et al. The method we present is interesting in its own right and can be applied to any external memory pointer based data structure with maximum in-degree din bounded by a constant and out-degree bounded by O(B), where every node occupies a constant number of blocks on disk. The I/O-overhead per modification to the ephemeral structure is O(din log2 B) amortized I/Os, and the space overhead is O(din/B) amortized blocks. Access to a field of an ephemeral block is supported in O(log2 din) worst case I/Os.

Anomaly detection is considered an important data mining task, aiming at the discovery of elements (also known as outliers) that show significant diversion from the expected case. More specifically, given a set of objects the problem is to return the suspicious objects that deviate significantly from the typical behavior. As in the case of clustering, the application of different criteria lead to different definitions for an outlier. In this work, we focus on distance-based outliers: an object x is an outlier if there are less than k objects lying at distance at most R from x. The problem offers significant challenges when a stream-based environment is considered, where data arrive continuously and outliers must be detected on-the-fly. There are a few research works studying the problem of continuous outlier detection. However, none of these proposals meets the requirements of modern stream-based applications for the following reasons: (i) they demand a significant storage overhead, (ii) their efficiency is limited and (iii) they lack flexibility. In this work, we propose new algorithms for continuous outlier monitoring in data streams, based on sliding windows. Our techniques are able to reduce the required storage overhead, run faster than previously proposed techniques and offer significant flexibility. Experiments performed on real-life as well as synthetic data sets verify our theoretical study.

This work studies the problem of 2-dimensional searching for the 3-sided range query of the form [a, b] x (-∞, c] in both main and external memory, by considering a variety of input distributions. A dynamic linear main memory solution is proposed, which answers 3-sided queries in O(log n + t) worst case time and scales with O (log log n) expected with high probability update time, under continuous μ-random distributions of the x and y coordinates, where n is the current number of stored points and t is the size of the query output. Our expected update bound constitutes a considerable improvement over the O(log n) update time bound achieved by the classic Priority Search Tree of McCreight [23], as well as over the Fusion Priority Search Tree of Willard [30], which requires O(log n/log log n) time for all operations. Moreover, we externalize this solution, gaining O(logB n + t/B) worst case and O(logBlogn) amortized expected with high probability I/Os for query and update operations respectively, where B is the disk block size. Then, combining the Modified Priority Search Tree [27] with the Priority Search Tree [23], we achieve a query time of O(log log n + t) expected with high probability and an update time of O(log log n) expected with high probability, under the assumption that the x-coordinates are continuously drawn from a smooth distribution and the y-coordinates are continuously drawn from a more restricted class of distributions. The total space is linear. Finally, we externalize this solution, obtaining a dynamic data structure that answers 3-sided queries in O(logB log n + t/B) I/Os expected with high probability, and it can be updated in O(logB log n) I/Os amortized expected with high probability and consumes O(n/B) space, under the same assumptions.

We focus on range query processing on large-scale, typically distributed infrastructures. In this work we present the ART (Autonomous Range Tree) structure, which outperforms the most popular decentralized structures, including Chord (and some of its successors), BATON (and its successor) and Skip-Graphs. ART supports the join/leave and range query operations in O(log log N) and O(log2b logN +|A|) expected w.h.p number of hops respectively, where the base b is a double-exponentially power of two, N is the total number of peers and |A| the answer size.

In this paper we introduce a novel distributed simulation environment with GUI for P2P simulations (D-P2P-Sim). The key aim is to provide the appropriate integrated set of tools in a single software solution to evaluate the performance of various protocols. The basic architecture of the distributed P2P simulator is based on a multi-threading, asynchronous, message passing and distributed environment with graphical user interface to facilitate ease of use by both researchers and programmers.

We present a time-efficient approach to index objects moving on the plane to efficiently answer range queries about their future positions. Each object is moving with non small velocity u, meaning that the velocity value distribution is skewed (Zipf) towards umin in some range [umin, umax], where umin is a positive lower threshold. Our algorithm enhances a previously described solution [18] by accommodating the ISB-tree access method as presented in [6]. Experimental evaluation shows the improved performance, scalability and efficiency of the new algorithm.

A multirepeat in a string is a substring (factor) that appears a predefined number of times. A multirepeat is maximal if it cannot be extended either to the right or to the left and produce a multirepeat. In this paper, we present algorithms for two different versions of the problem of finding maximal multirepeats in a set of strings. In the case of arbitrary gaps, we propose an algorithm with O ( σN2n + α ) time complexity. When the gap is bounded in a small range c , we propose an algorithm with O (( c2 + σ2 ) mN2n log( Nn ) + α ) time complexity. Here, N is the number of strings, n the mean length of each string, m the multiplicity of the multirepeat and α the number of reported occurrences. Our results extend previous work by considering sets of strings as well as by generalizing pairs to multirepeats.

We develop a new finger search tree with worst-case constant update time in the Pointer Machine (PM) model of computation. This was a major problem in the field of Data Structures and was tantalizingly open for over twenty years while many attempts by researchers were made to solve it. The result comes as a consequence of the innovative mechanism that guides the rebalancing operations combined with incremental multiple splitting and fusion techniques over nodes.