Protein classification is a key challenge in bioinformatics, essential for understanding biological functions, molecular interactions, and drug discovery. Yet, the functional landscape of proteins cannot always be inferred from sequence or fold similarity, as structurally divergent proteins may share common biological roles. Since most molecular interactions occur at the protein surface, capturing the geometric and biochemical features of these surfaces is essential for accurate functional inference. In this work, we introduce ProCLR, a graph-based framework that models protein surfaces as simplified, attribute-rich 3D geometric graphs, and applies supervised contrastive learning to learn discriminative embeddings. Our method integrates a geodesicaware clustering strategy to reduce surface complexity while preserving functional features. We evaluate ProCLR using two encoder architectures-Graph Convolutional Networks (GCNs) and Graph Attention Networks (GATs)-on the SHREC'21 and SHREC'19 benchmarks. Experimental results show that ProCLR effectively captures functional patterns, achieving competitive performance with significantly reduced graph sizes, as measured by sensitivity, specificity, precision, accuracy, and F1-score.

In this work, we introduce a novel method to enhance 3D mesh representations of protein surfaces by emphasizing edge-level information. Our approach incorporates both the angles formed by edges and the degrees of the vertices they connect. This additional geometric and topological information enriches the mesh encoding, providing a finer understanding of local connectivity and spatial organization. Such reinforcement proves especially beneficial in tasks requiring the discrimination of subtle structural variations. We demonstrate the effectiveness of our strategy in the context of protein surface analysis, where the 3D shape plays a critical role in biological function. By treating proteins as mesh-based structures, our method offers a more expressive and discriminative representation, enabling improved performance on downstream tasks such as classification or binding site prediction.

Identifying important nodes in networked systems is crucial for network analysis and many other applications. Different metrics have been used to assess the node importance within a network, generally as a property to be fulfilled by the node deletion. In this work, we consider as important nodes those whose deletion partitions the network into connected components of a given size. Given the graph G representing the network, we look for the smallest subset of nodes whose removal partition G into components of at most κ nodes, where κ is a given bound. This problem has already been shown to be NP-complete even when restricted to particular classes of graphs, which is the case for general chordal graphs. In this paper, we develop a polynomial-time algorithm to solve it on chordal graphs with maximum node degree Δ = 3. The proposed algorithm returns an exact solution in O(n2) for a graph G of n nodes.

Over the last decade, graphs have gained in popularity and have been widely used to model complex real world structures and data in various application domains. This leads to a rapid proliferation of large graph databases with hundreds of millions of nodes and edges. Thus, graph querying becomes a major problem that emerges from these collections of graphs. However, the current approaches for graph matching fail if no single graph satisfies all requirements of a query. In this paper, we present a novel approach for graph matching, where a new graph is constructed from fragments of other graphs. As a result, several relevant graph fragments are assembled and presented as solution. The proposed approach returns the best aggregated graph that fulfils as much as possible the query requirements, instead of returning a ranked list of graphs. We analyse the execution time of the proposed solution and conduct experimental evaluations to measure its effectiveness compared to several graph matching algorithms. The results show the good performance of the proposed approach.

In this paper, we study the behavioral communication patterns of employees in the last few months before they quit their company. Our study is based on Slack communication metadata from two technology companies. We analyse the communication patterns of terminated employees in the last 15 months before they left the organisation. We use different metrics such as the volume of messages sent, the activity in different channels, the average range of communication, and the number of collaborators over time. We also compare the behavior of the employees who are about to quit versus the company average in the same time period. We discover that there is a clear communication pattern for employees who quit with a pronounced decrease of engagement in the last 5 to 6 months before they left. We then build a machine learning model to predict if an employee is at risk of leaving the company within the next 6 months.

Protecting network applications against malicious behaviors is one of the main concerns when designing network applications. A secured application must take into account any network weakness that an attacker may exploit. One of the major weaknesses is network disconnectivity. A network becomes disconnected by removing nodes/links. This nodes/links are those those that maintain the whole network connectivity, and known as the critical elements. In this paper, we consider the problem of finding critical nodes in networks, which is a good way to assess network vulnerability. This problem consists in finding the smallest subset of nodes, in a given network, the deletion of which partitions it into connected components of the minimum cardinality. We investigate the problem complexity on the class of networks modeled by split graphs, where we show that it remains NP-hard, and hence heuristic approaches are well-suitable for finding near optimal solutions.

Attrition prediction research typically focuses on constructing models that involves one observation per employee over a limited time period, while the rest of the employees are discarded.Time-series attributes are transformed to non-time-series ones by applying statistical operations (e.g.sum, max, etc.).Such methods result in information loss and therefore less effective predictions.In this paper, we introduce a dynamic approach to employee attrition prediction, leveraging the longitudinal nature of the data, and allowing the models to generalize across behaviors and providing a closer estimate of the employee risk of leaving.53

The monitoring of mobile ad hoc networks is an observation task that consists of analysing the operational status of these networks while evaluating their functionalities. In order to allow the whole network and applications to work properly, the monitoring task has become of considerable importance. It must be carried out in real-time by performing measurements, logs, configurations, etc. However, achieving continuous energy-efficient monitoring in mobile wireless networks is very challenging considering the environment features as well as the unpredictable behavior of the participating nodes. This paper outlines the challenges of continuous energy-efficient monitoring over mobile ad hoc networks. We propose two strategies that can reduce the energy consumption and extend the lifetime of the monitoring system. We also formulate the continuous monitoring problem decision as a Markov Decision Process (MDP). The experimental results obtained by simulations, clearly show that our proposals can reduce significantly the energy consumption and increase the whole network lifetime.

International audience

Time series have met high interest in various fields for measuring the evolution of a quantity over time. Several machine learning techniques are proposed to extract knowledge from this type of data and make them more meaningful. Clustering is one such prominent technique, for detecting homogeneous subgroups from a data set when there is no prior knowledge about classes. It has been called upon various fields to discover hidden models that arise from the data. In this paper, we propose a new framework called Generative time series Clustering with Bagging (GCBag). It combines the power of several techniques designed for time series. Most existing works use DTW to provide a starting point for HMMs to estimate their parameters. As a result, the estimation becomes dependent on this single provided initialization, which can be biased. The originality of GCBag lies in the use of bagging during the clustering where it significantly raises the stability of models. Consequently, we have succeeded in improving the quality of clustering while preserving the descriptive aspect. Several experiments are conducted to demonstrate the effectiveness of GCBag over the existing models for time series clustering, on both synthetic and real time series data.

We propose a novel fast graph matching approach based on a new formulation of the stable marriage problem, to measure the distance between graphs. The proposed approach is optimal in terms of execution time, i.e. quadratic time complexity O(n2). Our technique is based on the decomposition of graphs into a set of substructures which are subsequently matched with the stable marriage algorithm. In this paper, we address the problem of comparing deformable 3D objects represented by graphs, we use a triangle-stars decomposition for triangular tessellations (graphs of 3D shapes). The proposed approach is based on computing an approximation of Graph Edit Distance which is fault-tolerant to noise and distortion which makes our method especially relevant for deformable 3D shapes comparison. We analyze and determine its time complexity. The proposed method is evaluated against benchmark databases under different evaluation criteria. Our experimental results consistently demonstrate the effectiveness and the high performances of our approach.

International audience

Graph pattern matching has been widely used in large spectrum of real applications. In this context, different models along with their appropriate algorithms have been proposed. However, a major drawback on existing models is their limitation to find meaningful matches resulting in a number of failing queries. In this paper we introduce a new model for graph pattern matching allowing the relaxation of queries in order to avoid the empty-answer problem. Then we develop an efficient algorithm based on optimization strategies for computing the top k matches according to our model. Our experimental evaluation on four real datasets demonstrates both the effectiveness and the efficiency of our approach.

Graph querying is crucial to fully exploit the knowledge within the widely used graph datasets.However, graph datasets are usually noisy which makes the approximate graph matching tools favored to overcome restrictive query answering.In this paper, we introduce a new framework of approximate graph matching based on aggregated search called Label and Structure Similarity Aggregated Search (LaSaS).LaSaS enables effective and efficient graph querying without considering any fixed schema of the data graph by (i) using the aggregated search strategy to increase the number of answers, (ii) using a lightweight graph similarity metric that takes into account nodes label and graph structure similarity to enable finding approximate matches and also by (iii) using a simple graph weight update routine instead of computing the maximum common subgraph which reduces the overall computation cost.We evaluated our proposed approach over the real-life DBpedia graph and results show the effectiveness and stability of the approach on different parameter settings.Moreover, results also show that LaSaS yields more precise matches in a shorter amount of time when compared to state-of-the-art related approaches.

The proliferation in size of actual graph datasets impels the use of distributed graph processing frameworks which in turn, should consider a good partitioning of the graph dataset in order to see their performances enhanced. In this paper, we focus on a well known heuristic for graph partitioning named METIS, an offline method giving high quality partitions but unsuitable for processing large graphs due to the offline setting. A recently proposed alternative is the streaming partitioning heuristics aiming to alleviate the computational resources constraints when dealing with large graphs. In considering this matter, we propose a new partitioning method that benefits from the accuracy of METIS and the lightness of the streaming setting. This work introduces the Streaming METIS Partitioning method (SMP) which is an online counterpart of METIS, a fast and well known multilevel heuristic for graph partitioning. We show in a complexity analysis that SMP has a lower time complexity compared to METIS, which is confirmed by conducted experiments. Moreover, we show that SMP yields competitive results to its offline counterpart METIS, especially when it is run on a Depth First Search streaming order. Also, when compared to other online competitors, SMP is the best performing heuristic giving partitions with minimal edge cut.

We consider the problem of comparing deformable 3D objects represented by graphs, i.e., Triangular tessellations. We propose a new algorithm to measure the distance between triangular tessellations using a new decomposition of triangular tessellations into triangle-Stars. The proposed algorithm assures a minimum number of disjoint triangle-Stars, offers a better measure by covering a larger neighborhood and uses a set of descriptors which are invariant or at least oblivious under most common deformations. We prove that the proposed distance is a pseudo-metric. We analyse its time complexity and we present a set of experimental results which confirm the high performance and accuracy of our algorithm.

We present GraphExploiter, a tool to import, visualize and manage data by representing them in a graph structure. The aim of this platform is (i) to facilitate the creation of graphs from real data sets, (ii) to propose an efficient tool of scalable visualization and (iii) to allow a user to import easily its own graph algorithms to the platform.

Graph partitioning is an important challenging problem when performing computation tasks over large distributed graphs; the reason is that a good partitioning leads to faster computations. In this work, we first introduce a new heuristic for streaming partitioning and show that it outperforms the state-of-the-art heuristics for streaming partitioning, leading to exact balance and lower cut. Secondly, we introduce the partial restreaming partitioning which is a hybrid streaming model allowing only several portions of the graph to be restreamed while the rest is to be partitioned on a single pass of the data stream. We show that our method yields partitions of similar quality than those provided by methods restreaming the whole graph (e.g ReLDG, ReFENNEL), while incurring lower cost in running time and memory since only several portions of the graph will be restreamed.

Abstract Motivated by the problem of link scheduling in wireless sensor networks where different sensors have different transmission and interference ranges and may be mobile, we study the problem of “distance edge coloring” of graphs, which is a generalization of proper edge coloring. Let Gbe a graph modeling a sensor network. An ℓ‐distance edge coloring of Gis a coloring of the edges of Gsuch that any two edges within distance ℓof each other are assigned different colors. The parameter ℓis chosen, so that the links corresponding to two edges that are assigned the same color do not interfere. We investigate the ℓ‐distance edge coloring problem on several families of graphs that can be used as topologies in sensor deployment. We focus on determining the minimum number of colors needed and optimal coloring algorithms. © 2013 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 2013

Collaborative recommender systems are systems which recommend to a user resources may be of his interests based on the opinions of other users who share with him the same center of interest. However, they suffer from the cold start problem of a new user who starts with an empty profile and encounters a difficulty of communication with his community members. In this paper, we propose a new approach to overcome the latter problem by modeling it graphically and by opting for the detection of critical nodes to identify the best representatives that help to adapt a new user in each social community.

Mobile ad hoc networks are deployed in many new domestic and public applications, rising to new requirements in terms of performance and efficiency. However, some of its characteristics pose a significant challenge to the monitoring of ad hoc networks. In particular, designing and implementing a monitoring solution that is capable of providing up-to-date information regarding the network's overall health remains a challenge. Therefore in this paper we propose HMAN, Hierarchical Monitoring for Ad hoc Network.

Lifetime optimization becomes a commonplace feature of wireless sensor networks. In addition, as the scale is expanding, node reliabilities gradually become dynamically heterogeneous over time even if sensor nodes are symmetric by design. At the same time, as sensor nodes get smaller and approach technological limits, they suffer from increased susceptibility to wear-out which becomes a real problem as complex sensor networks with many nodes operate in unsafe and harsh environments for long times. Con sequently, there is an increasing need for developing techniques to achieve more reliability, i.e., increase the net work's operational time. In this paper, we introduce an efficient distributed failure-aware strategy (on-line solution) using probabilistic Weibull distribution to resist to frequent and unexpected fail-silent/fail-stop node failures. We provide a comprehensive set of experimental results, that fully demonstrate the usefulness of the proposed solution.

With the development of e-commerce over Internet, web service discovery received much interest. A critical aspect of web service discovery is web service similarity search or matchmaking. To enhance the similarity precision, several solutions that do not limit to a syntactic comparison of inputs and outputs of the compared services have been proposed. Most of them introduce the structure of web service operations in the similarity measure. In this paper, we analyze these approaches and point out their time complexity drawback. Then, we propose a more efficient matching algorithm based on the concept of decomposition kernels of graphs. We study the complexity of our approach and present performance analysis.

The study of emerged community structures is an important challenge in networks analysis. In fact, several methods have been proposed in the literature to statistically determine the signification of discovered structures. Nevertheless, most of existing analysis models consider only the structural aspect of emerged communities. In our study, we give interest to robustness study of emerged communities in resource exchange networks. More precisely, we consider the emerged communities in the induced graph by all the exchanges in these networks. Hence, rather than examining the robustness only on the structural properties of the graph, we give focus to the parameters that allow the emergence of community structures. In fact, perturbing these parameters might destroy most of the obtained properties at the emerged level. To the best of our knowledge, robustness of networks has never been considered from this angle before. In this paper, we study the impact of perturbing the content, the interest and the profile of nodes on the emerged social communities in resource exchange networks. We show how these alterations affect both structure and information supported by the emerged structures.

If we draw the virtual topology representing the communication in networks, we observe that the structure is similar to those of the social networks. Social networks are these networks with the characteristic relating densely some entities than others. These dense zones are called communities. Generally, the members of a same community share the same interest. In this work, we look for which virtual topology (called communication graph) emerged in communication network gives communities closer to the real one. Three different communication graphs are generated and compared with the graph representing the real communities, the reference graph. Microscopic and macroscopic comparisons are done.

Topology Control (TC) is a well known technique used in wireless ad hoc and sensor networks to reduce energy consumption. This technique coordinates the decisions of network nodes about their transmission power to save energy, prolong network lifetime, and mitigate MAC-level medium contention, while maintaining network connectivity. In order to ease the implementation and the study in systematic way of proposed TC protocols, in terms of energy usage and network graph properties, we propose a new framework based on NS-2 simulator. The framework is named TopCoF and composed of two main parts. The first one consists of a set of NS-2 extensions to support TC, while the second is a graphical user interface for statistical analysis and visualization of simulation results traced by the first part. TopCoF is modular and generic since it implements a set of basic components used by TC protocols.

In this paper, we deal with the problem of distributed data fusion in unsafe large-scale sensor networks. Data fusion application is the phase of processing the collected data by sensor nodes before sending it the end user. During this phase, resource failures are more likely to occur and can have an adverse effect on the application. Hence, we introduce first an efficient self-stabilizing algorithm to achieve/ensure the convergence of node states to the average of the initial measurements of the network. Next, we present a fault tolerant scheme to resist to frequent and unexpected not concomitant fail-silent/fail-stop node failures. The major contribution of this paper is the design of an analytical expression (an upper bound) of the actual number of moves/iterations required by the algorithm. We provide a comprehensive set of experimental results, that fully demonstrate the usefulness of the proposed schemes.

A critical challenge in designing ad hoc networks is resource discovery. In this paper, we propose a resource discovery scheme for large scale ad hoc networks, which uses a hypercubes-based backbone. Hypercubes are constructed in the different localities of the network by considering closely its physical topology constraints and the hypercube multi-paths property. The constructed hypercubes are then connected to form a backbone. ADHT (Distributed Hash Table) is processed on these hypercubes to lookup and register the resources. To avoid overloading the resource discovery system, we propose a flexible mechanism where the dimension of every hypercube can be adapted according to the load. The efficiency and the contribution of our scheme are evaluated through extensive simulation and by comparison with well known existing resource discovery approaches.

The challenges in designing secure and scalable group key management solutions are dynamic updates of keys caused by member addition and member deletion. Most proposed solutions in the literature do not take this parameter into consideration and so suffer from the 1-affects-n scalability problem. In this paper, we present a group key management protocol that achieves a maximum of Log3n message exchange to rekey the group after a leave operation.

The social networks and the study of communities of interest became an actual challenge in several research areas. Community detection techniques have found a large number of practical applications as a method to simplify networks since the number of clusters is often much smaller than the number of nodes. In this paper, we study two aspects. In the first part, we focus on the induced social interactions by the communication between the individuals (peers) of a network in order to extract properties of the resultant community structures. Plenty of communication protocols were defined to allow and improve the data exchange between the different peers of the network [13][19][18]. The second part of our work concerns the study of the robustness of emerging communities.

Given a graph G = (V, E), an edge-coloring of G is a function from the set of edges E to colors {1, 2. .., k} such that any two adjacent edges are assigned different colors. In this paper, we propose a self-stabilizing edge-coloring algorithm in a polynomial number of moves. The protocol assumes the unfair central dæmon and the coloring is a (Δ + 1)-edge-coloring of G, where Δ is the maximum degree in G. To our knowledge, we give the first self-stabilizing edge-coloring algorithm using (Δ + 1) colors of arbitrary graphs.

A b-coloring of a graph G is a proper coloring of the nodes of G such that each color class contains a node that has a neighbor in all other color classes. A fully dynamic algorithm is an algorithm used to support modifications (insertion or deletion) of nodes and edges in a network. Thus, in this paper we propose a fully dynamic distributed algorithm to maintain a b-coloring of a graph when its topology evolves. This method determines a b-coloring in time O(¿2) and needs O(n¿) changes of colors to maintain a b-coloring of a graph, where n is the number of nodes and ¿ is the maximum degree in the graph.

We have given necessary and sufficient conditions which is an extention of Thomassen's characterization of the rectangular drawing of plane graphs with maximum vertex degree four. A drawing algorithm is also proposed.