Pasar al contenido principal

MODELOS Y TECNICAS PARA EL PROCESAMIENTO DE INFORMACION A GRAN ESCALA -- BARCELONA

PID2020-112581GB-C21

•
Nombre agencia financiadora Agencia Estatal de Investigación
Acrónimo agencia financiadora AEI
Programa Programa Estatal de I+D+i Orientado a los Retos de la Sociedad
Convocatoria Proyectos de I+D+i (Generación de Conocimiento y Retos Investigación)
Año convocatoria 2020
Plan Estatal 2017-2020 Plan Estatal de Investigación Científica y Técnica y de Innovación
Centro beneficiario UNIVERSITAT POLITECNICA DE CATALUNYA

Resultados relacionados

Resultados totales (Incluyendo duplicados): 111
Encontrada(s) 2 página(s)

RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Capítulo o parte de un libro (BookPart)

Take the Challenge: Compute the CO2e emissions of your Programming Course

  • Gabarró, Joaquim
  • Blesa, Maria Josep
  • Duch, Amalia
  • Serna, Maria
[EN] Sustainability constraints ask for quick and drastic changes in the ways to teach at university. Here we study the amount of carbon emissions of lecturing a first course in programming. In addition to fix costs estimations, our study relies on a pool on student mobility patterns at our university. We estimate, per campus and level of presentiality, the amount of CO2e emissions of the course. Our results show that the main contributed cost of the course is not always due to transportation. Indeed, the difference in emissions between virtual and face-to-face is not huge and in some cases face-to-face is even better. This offers a discussion about the convenience of replacing face-to-face by virtual teaching through minimizing transportation emissions. We claim that the former can be made CO2e competitive by disseminating the lectures across the city avoiding the use of costly traveling means., This work was partially supported by the Spanish Agencia Estatal de Investigación, under grant PID2020-112581GB-C21 (MOTION).
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Artículo científico (JournalArticle)

AntNetAlign: Ant Colony Optimization for Network Alignment

  • Rodríguez-Corominas, Guillem
  • Blum, Christian
  • Blesa, María Jesús
Network Alignment (NA) is a hard optimization problem with important applications such as, for example, the identification of orthologous relationships between different proteins and of phylogenetic relationships between species. Given two (or more) networks, the goal is to find an alignment between them, that is, a mapping between their respective nodes such that the topological and functional structure is well preserved. Although the problem has received great interest in recent years, there is still a need to unify the different trends that have emerged from diverse research areas. In this paper, we introduce AntNetAlign, an Ant Colony Optimization (ACO) approach for solving the problem. The proposed approach makes use of similarity information extracted from the input networks to guide the construction process. Combined with an improvement measure that depends on the current construction state, it is able to optimize any of the three main topological quality measures. We provide an extensive experimental evaluation using real-world instances that range from Protein–Protein Interaction (PPI) networks to Social Networks. Results show that our method outperforms other state-of-the-art approaches in two out of three of the tested scores within a reasonable amount of time, specially in the important score. Moreover, it is able to obtain near-optimal results when aligning networks with themselves. Furthermore, in larger instances, our algorithm was still able to compete with the best performing method in this regard., Christian Blum and Guillem Rodríguez Corominas, Spain were supported by grants PID2019-104156GB-I00 and TED2021-129319B-I00 funded by MCIN/AEI/10.13039/501100011033. Maria J. Blesa acknowledges support from AEI, Spain under grant PID-2020-112581GB-C21 (MOTION) and the Catalan Agency for Management of University and Research Grants (AGAUR), Spain under grant 2017-SGR-786 (ALBCOM)., Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Artículo científico (JournalArticle)

Accelerating the k-Means++ Algorithm by Using Geometric Information

  • Rodríguez Corominas, Guillem
  • Blesa, Maria J.
  • Blum, Christian
Clustering is a fundamental task in data analysis with applications across a wide range of fields, such as computer vision, pattern recognition, and data mining. Real-world use cases include social network analysis, medical imaging, market segmentation, and anomaly detection, to name a few. In this paper, we propose an acceleration of the exact k-means++ algorithm using geometric information, specifically the Triangle Inequality and additional norm filters, along with a two-step sampling procedure. Our experiments demonstrate that the accelerated version outperforms the standard k-means++ version in terms of the number of visited points and distance calculations, achieving greater speedup as the number of clusters increases. The version utilizing the Triangle Inequality is particularly effective for low-dimensional data, while the additional norm-based filter enhances performance in high-dimensional instances with greater norm variance among points. Additional experiments show the behavior of our algorithms when executed concurrently across multiple jobs and examine how memory performance impacts practical speedup., This work was supported in part by the Department of Research and Universities of the Government of Catalonia by means of an European Social Fund (ESF)-Founded Pre-Doctoral Grant of the Catalan Agency for Management of University and Research Grants (AGAUR) under Grant 2022 FI_B 00903, in part by the Agencia Estatal de Investigación (AEI) under Grant PID-2020-112581GB-C21 (MOTION), in part by Ministerio de Ciencia e Innovación (MCIN)/AEI/10.13039/501100011033 under Grant TED2021-129319B-I00 and Grant PID2022-136787NB-I00, and in part by the European Commission–NextGenerationEU, through Momentum CSIC Programme: Develop Your Digital Talent, under Project MMT24-IIIA-02., Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Artículo científico (JournalArticle)

SoftBinReduce: data reduction for color quantization through soft binning

  • Rodríguez-Corominas, Guillem
  • Blesa Aguilera, María Jesús;
  • Blum, Christian
For detailed results, interested parties can request information from the corresponding author. The CQ100 dataset used for the experimental evaluation is available at https://doi.org/10.17632/vw5ys9hfxw.2. The USC-SIPI dataset is available at https://sipi.usc.edu/database/database.php?volume=misc. The Kodak dataset is available at: https://r0k.us/graphics/kodak., In this paper, we propose SoftBinReduce, a data reduction method for Color Quantization. Our approach consists of four main steps: (1) identifying representatives in each channel, (2) generating three-dimensional bins, (3) distributing pixel values using a soft binning technique, and (4) repositioning the resulting bins. Additionally, we introduce an adapted Sort-Means algorithm for the Pixel Mapping phase, providing a strong initial guess. We conduct an extensive experimental evaluation primarily using the CQ100 dataset, but also the older Kodak and USC-SIPI datasets. We compare our method to two well-known data reduction techniques from the literature: pseudo-random and quasi-random sampling. The results demonstrate that our method outperforms both in terms of NMSE error versus the achieved speedup, particularly when the data is significantly reduced and with a higher number of colors in the generated palette. Moreover, an ablation study shows that all components of our method are necessary for producing high-quality results., Open Access funding provided thanks to the CRUE-CSIC agreement with Springer Nature. Guillem Rodríguez Corominas acknowledges support from the Department of Research and Universities of the Government of Catalonia by means of an ESF-founded pre-doctoral grant of the Catalan Agency for Management of University and Research Grants (AGAUR), under ref. number 2022 FI_B 00903. Maria J. Blesa acknowledges support from AEI under MICINN grant PID-2020-112581GB-C21 (MOTION). Christian Blum was supported by two grants funded by MCIN/AEI/10.13039/501100011033: TED2021-129319B-I00 and PID2022-136787NB-I00., We acknowledge administrative and technical support by the Spanish National Research Council (CSIC) and by the Universitat Politècnica de Catalunya (UPC)., Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Artículo científico (JournalArticle)

AntNetAlign—A software package for Network Alignment

  • Rodríguez-Corominas, Guillem
  • Blesa, María Jesús
  • Blum, Christian
Original software publication., In this paper we introduce AntNetAlign, an open-source tool (written in C++) that implements an Ant Colony Optimization (ACO) for solving the Network Alignment (NA) problem, a well-known hard optimization problem with important applications in different areas, such as biology or social networks. Specifically, given two input networks, the tool finds an alignment between them (i.e., a mapping between the respective nodes) that optimizes one out of the three main topological measures. Additionally, it can make use of user-defined pairwise similarities between nodes during its construction phase, allowing for the use of more application-dependent information in order to increase its performance. Results show that AntNetAlign outperforms other state-of-the-art algorithms in two out of the three aforementioned topological scores within a reasonable amount of time, and is able to achieve competitive results in the context of larger instances (Rodríguez Corominas et al., 2023). Furthermore, a new version of the algorithm, which makes use of Negative Learning, was able to further improve these results, specially in the EC score (Corominas et al., 2022)., Guillem Rodríguez Corominas gets support from the Department of Research and Universities of the Government of Catalonia by means of an ESF-founded pre-doctoral grant of the Catalan Agency for Management of University and Research Grants (AGAUR, Catalonia, Spain), under ref. number 2022 FI_B 00903. Christian Blum was supported by two grants funded by MCIN/AEI/10.13039/501100011033: AEI, Spain PID2019-104156GB-I00, and TED2021-129319B-I00. Maria J. Blesa acknowledges support from AEI, Spain under grant PID-2020-112581GB-C21 (MOTION) and the Catalan Agency for Management of University and Research Grants (AGAUR , Catalonia, Spain), under grant 2021-SGR-01419 (ALBCOM)., Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Otros (Other)

Tight Bounds for an Accelerated k-means++ Algorithm

  • Rodríguez-Corominas, Guillem
  • Blesa Aguilera, María Jesús
  • Blum, Christian
21st IFIP WG 12.5 International Conference, AIAI 2025, Limassol, Cyprus, June 26–29, 2025, Proceedings, Part I, Conference proceedings. IFIP (International Federation for Information Processing)., In this paper, we improve a recently introduced accelerated k-means++ algorithm by proposing a dynamic method for calculating bounds during its execution. This approach produces high-quality bounds without requiring a full iteration over the dataset, using the Triangle Inequality and the norm of the points for efficient computation. We propose three evaluation metrics to assess the quality of the calculated bounds and analyze their behavior across a diverse dataset. Results show that this dynamic method outperforms the traditional approach of initializing bounds at the end of the process, before the execution of the -means algorithm., The research presented in this paper was supported by grant 2022 FI_B 00903 funded by the AGAUR; grant PID-2020-112581GB-C21 (MOTION) funded by the AEI; grants TED2021-129319B-I00 and PID2022-136787NB-I00 funded by MCIN/AEI/10.13039/501100011033; and project MMT24-IIIA-02 funded by Red.es, Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Artículo científico (JournalArticle)

FastKPP: An exact accelerated k[jls-end-space/]-means(Formula presented) algorithm

  • Rodríguez-Corominas, Guillem
  • Blesa Aguilera, María Jesús
  • Blum, Christian
In this paper, we present FastKpp, a C++ implementation of an exact accelerated k[jls-end-space/]-means(Formula presented) algorithm using two geometry-aware filters: one based on the Triangle Inequality (TIE) and another based on point norms. Both provably preserve the original D 2 sampling distribution while avoiding redundant distance computations. The library provides a header-only API, a command-line tool, and a fully reproducible capsule. Experiments show substantial reductions in distance computations and speedups that increase with k (with typical median between 2 and 8). Furthermore, FastKpp outperforms other state-of-the-art exact acceleration techniques. Results are reproducible via the public GitHub repository and Code Ocean capsule., This work was supported in part by the Department of Research and Universities of the Government of Catalonia by means of an European Social Fund (ESF)-Founded Pre-Doctoral Grant of the Catalan Agency for Management of University and Research Grants (AGAUR) under Grant [2022 FI_B 00903](https://www.sciencedirect.com/science/article/pii/S2665963826000205?via%3Dihub#GS1), in part by the Agencia Estatal de Investigación (AEI) under grants [PID-2020-112581GB-C21 (MOTION)](https://www.sciencedirect.com/science/article/pii/S2665963826000205?via%3Dihub#GS2) and [PID2022-136787NB-I00 (ACISUD)](https://www.sciencedirect.com/science/article/pii/S2665963826000205?via%3Dihub#GS2), and in part by the European Commission–NextGenerationEU, through Momentum CSIC Programme: Develop Your Digital Talent , under Project [MMT24-IIIA-02](https://www.sciencedirect.com/science/article/pii/S2665963826000205?via%3Dihub#GS3)., Peer reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

NTAC: Neuronal type assignment from connectivity

  • Schwartzman, Gregory
  • Jourdan, Ben
  • García Soriano, David|||0000-0002-2869-9330
  • Matsliah, Arie
Recent advances in electron microscopy and computer vision now allow the reconstruction of complete wiring diagrams, or connectomes, of animal brains. This creates an urgent need for methods that can automatically identify neuronal cell types directly from these large connectivity datasets. Here we show that synaptic connectivity alone can be used to assign neurons to cell types with high accuracy. We introduce NTAC (Neuronal Type Assignment from Connectivity), which groups neurons based only on connectivity. NTAC has two forms: a semi-supervised one that leverages a small fraction of labeled neurons to infer the types of all others, and an unsupervised one that requires no labels at all. Applied to multiple state-of-the-art fruit fly brain connectomes, NTAC achieves high accuracy within only minutes on a laptop, demonstrating that connectivity provides a powerful and scalable basis for classifying neuronal cell types across the brain., AM was supported by funding provided through grants to Murthy and Seung from the NIH BRAIN Initiative (RF1 MH117815, RF1 MH129268, U24 NS126935). GS was supported by the following research grants: KAKENHI 25K00370, JST ASPIRE JPMJAP2302 and JST CRONOS JPMJCS24K2. BJ was supported through an EPSRC Early Career Fellowship (EP/T00729). DGS was supported by the Spanish Agencia Estatal de Investigación AEI/10.13039/ 501100011033 (Project PID2020-112581GB-C21 MOTION)., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Typeface recognition and legibility metrics

  • Molinero Albareda, Xavier|||0000-0002-5203-4347
  • Tàpias Anton, Montserrat|||0000-0003-2421-0718
  • Balius Planelles, Andreu
  • Salvadó Arqués, Francisco María
In the digital age, people prefer digital content, but screen-related health concerns like eye strain and blue light emerge. Legibility gains importance in digital text, especially in fields like optometry and for those with low vision. Therefore, having good letter recognition ensures better readability of words and written language in general. This work focuses on defining three typeface legibility indices from the judgements of a group of 31 observers. Those indices are based on statistics, confusion matrices, and power indices from game theory. As far as we know, this is the first time that typeface legibility indices have been defined using game theory. These indices help us to globally assess how legible is a typeface. We apply them to three commonly used typefaces (Roboto, Helvetica and Georgia), and to a new one developed for the authors (Optotipica 5 v2022). This comparison helps us understand which typefaces are more legible according to the defined indices on digital screens. The major conclusions are: (1) The three indices are highly consistent pairwise; (2) Helvetica is the most legible typeface for uppercase letters, whilst Optotipica is the most legible for lowercase; (3) the two cases of Helvetica exhibit uniform high legibility metrics, ensuring optimal recognition regardless of letter case., X. Molinero was partially supported by the Spanish Ministry of Economy and Competitiveness (MINECO) and the European Union (FEDER funds) [PID2019-104987GB-I00, JUVOCO], the Spanish Agencia Estatal de Investigación [PID-2020-112581GB-C21, MOTION] and the Catalan government [2021 SGR 01419 ALBCOM], Peer Reviewed, Objectius de Desenvolupament Sostenible::1 - Fi de la Pobresa, Objectius de Desenvolupament Sostenible::3 - Salut i Benestar, Objectius de Desenvolupament Sostenible::10 - Reducció de les Desigualtats, Objectius de Desenvolupament Sostenible::11 - Ciutats i Comunitats Sostenibles
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Multidimension: a dimensionality extension of simple games

  • Molinero Albareda, Xavier|||0000-0002-5203-4347
  • Riquelme Csori, Fabian Rolando|||0000-0003-4491-0148
  • Roura Ferret, Salvador|||0000-0003-4394-5939
  • Serna Iglesias, María José|||0000-0001-9729-8648
In voting theory and social choice theory, decision systems can be represented as simple games, i.e., cooperative games defined through their players or voters and their set of winning coalitions. The weighted voting games form a well-known strict subclass of simple games, where each player has a voting weight so that a coalition wins if the sum of weights of their members exceeds a given quota. Since the number of winning coalitions can be exponential in the number of players, simple games can be represented much more compactly as intersections or unions of weighted voting games. A simple game’s dimension (codimension) is the minimum number of weighted voting games such that their intersection (union) is the given game. It is known there are voting systems with a high (co)dimension. This work introduces the multidimension as the minimum size of an expression with intersections and unions on weighted voting games necessary to obtain the considered simple game. We generalize this notion to subclasses of weighted voting games and analyze the generative properties of these subclasses. We also characterize the simple games with finite generalized multidimension over the set of weighted voting games without dummy players. We provide a comprehensive classification for simple games up to a certain number of players. These results complement similar classification results for generalized (co)dimensions. Our results show how generalized multidimension allows representing more simple games and more compactly, even for a small number of players and for subclasses., "Xavier Molinero was partially supported by the Spanish Ministry of Economy and Competitiveness (MINECO) and the European Union (FEDER funds) [PID2019-104987GB-I00, JUVOCO]. Fabián Riquelme was supported by the Fondecyt de Iniciación 11200113 from ANID, Chile. Maria Serna was partially supported by the Spanish Agencia Estatal de Investigación [PID-2020-112581GB-C21, MOTION]. Xavier Molinero, Salvador Roura, and Maria Serna were also partially supported by the Catalan government [2021 SGR 01419 ALBCOM]", Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Coinductive techniques for checking satisfiability of generalized nested conditions

  • Stoltenow, Lara
  • König, Barbara
  • Schneider, Sven
  • Corradini, Andrea
  • Lambers, Leen
  • Orejas Valdés, Fernando|||0000-0002-3023-4006
We study nested conditions, a generalization of first-order logic to a categorical setting, and provide a tableau-based (semi-decision) procedure for checking (un)satisfiability and finite model generation. This generalizes earlier results on graph conditions. Furthermore we introduce a notion of witnesses, allowing the detection of infinite models in some cases. To ensure completeness, paths in a tableau must be fair, where fairness requires that all parts of a condition are processed eventually. Since the correctness arguments are non-trivial, we rely on coinductive proof methods and up-to techniques that structure the arguments. We distinguish between two types of categories: categories where all sections are isomorphisms, allowing for a simpler tableau calculus that includes finite model generation; in categories where this requirement does not hold, model generation does not work, but we still obtain a sound and complete calculus., Andrea Corradini: Research partially supported by the Italian MUR under the PRIN 20228KXFN2 “STENDHAL” and by the University of Pisa under the PRA 2022_99 “FM4HD”. Fernando Orejas: Research partially supported by MCIN/ AEI /10.13039/501100011033 under grant PID2020-112581GB-C21., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

The diameter of sum basic equilibria games

  • Abiad Monge, Aida
  • Álvarez Faura, M. del Carme|||0000-0003-2352-0546
  • Messegué Buisan, Arnau|||0000-0002-7425-7592
We study the sum basic network creation game introduced in 2010 by Alon, Demaine, Hajiaghai and Leighton. In this game, an undirected and unweighted graph G is said to be a sum basic equilibrium if and only if, for every edge uv and any vertex v′ in G, swapping edge uv with edge uv′ does not decrease the total sum of the distances from u to all the other vertices. This concept lies at the heart of the network creation games, where the central problem is to understand the structure of the resulting equilibrium graphs, and in particular, how well they globally minimize the diameter. In this sense, in 2013 Alon et al. showed an upper bound of 2O(√logn) on the diameter of sum basic equilibria, and they also proved that if a sum basic equilibrium graph is a tree, then it has diameter at most 2. In this paper, we prove that the upper bound of 2 also holds for bipartite graphs and even for some non-bipartite classes like block graphs and cactus graphs., Aida Abiad is supported by the Dutch Research Council through the grant VI.Vidi.213.085. Carme Àlvarez is partially supported by MCIN/ AEI/ 10.13039/501100011033 under Project PID2020-112581GB-C21 (MOTION), by the Spanish Agencia Estatal de Investigación [PID-2020-112581GB-C21, MOTION] and the Catalan government [2021 SGR 01419 ALBCOM]. Arnau Messegué is supported by grant 2021SGR-00434., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Traversal games in K-shell decomposition

  • Molinero Albareda, Xavier|||0000-0002-5203-4347
  • Riquelme Csori, Fabian Rolando|||0000-0003-4491-0148
  • Serna Iglesias, María José|||0000-0001-9729-8648
In network science, K-shell decomposition is a well-known method for efficiently identifying structural hierarchical shells or layers within a network. In this hierarchy, the innermost non-empty shell contains actors with the highest connectivity, while the peripheral shell includes actors with fewer connections or less integration into the network. Rather than considering the outer shells less relevant than the inner ones, this paper introduces K-shell traversal games, as a family of simple cooperative games, whose winning coalitions consist of actors connecting the outermost to the innermost layer of the hierarchical structure, facilitating the flow of information or resources to key representatives across different shells. We analyze several properties of these games, their coalitions, and actors (or players). We also study their efficient computation, as well as their potential real-world applications based on connectivity analysis across hierarchical network layers., This work has been partially supported by the Spanish Agencia Estatal de Investigación AEI/10.13039/501100011033 (Project PID2020112581GB-C21 MOTION). F. Riquelme was supported by the postdoctoral fellowship awarded by the Carolina Foundation (Spain) and the University of Valparaíso, Chile (2024–2025), to carry out a postdoctoral stay at the Polytechnic University of Catalonia., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Thresholds as mechanisms for weighting influence in the linear threshold rank

  • Blesa Aguilera, Maria Josep|||0000-0001-8246-9926
  • Dominguez Besserer, Alejandro
  • Serna Iglesias, María José|||0000-0001-9729-8648
Social networks are the natural space for the spreading of information and influence and have become a media themselves. Several models capturing that diffusion process have been proposed, most of them based on the Independent Cascade (IC) model or on the Linear Threshold (LT) model. The IC model is probabilistic while the LT model relies on the knowledge of an actor to be convinced, reflected in an associated individual threshold. Although the LT-based models contemplate an individual threshold for each actor in the network, the existing studies so far have always considered a threshold of 0.5 equal in all actors (i.e., a simple majority activation criterion). Our main objective in this work is to start the study on how the dissemination of information on networks behaves when we consider other options for setting those thresholds and how many network actors end up being influenced by this dissemination. For doing so, we consider a recently introduced centrality measure based on the LT model, the Forward Linear Threshold Rank (FwLTR), which is the natural interpretation of the Linear Threshold Rank on directed networks. We experimentally analyze the ranking properties for several networks in which the influence resistance threshold follows different schemes. Here we consider three different schemes: (1) uniform, in which all players have the same value; (2) random, where each player is assigned a threshold u.a.r. in a prescribed interval; and (3) determined by the value of another centrality measure on the actor. Our results show that the selection has a clear impact on the ranking, even quite significant and abrupt in some cases. We conclude that the social networks ranks that provide the best assignments for the individual thresholds are FwLTR and the well-known PageRank., Supported by MCIN/AEI/10.13039/501100011033 under grant PID2020-112581GB-C21 (MOTION)., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Extremal coalitions for influence games through swarm intelligence-based methods

  • Riquelme Csori, Fabian Rolando|||0000-0003-4491-0148
  • Olivares Ordenes, Rodrigo
  • Muñoz Peña, Francisco
  • Molinero Albareda, Xavier|||0000-0002-5203-4347
  • Serna Iglesias, María José|||0000-0001-9729-8648
An influence game is a simple game represented over an influence graph (i.e., a labeled, weighted graph) on which the influence spread phenomenon is exerted. Influence games allow applying different properties and parameters coming from cooperative game theory to the contexts of social network analysis, decision-systems, voting systems, and collective behavior. The exact calculation of several of these properties and parameters is computationally hard, even for a small number of players. Two examples of these parameters are the length and the width of a game. The length of a game is the size of its smaller winning coalition, while the width of a game is the size of its larger losing coalition. Both parameters are relevant to know the levels of difficulty in reaching agreements in collective decision-making systems. Despite the above, new bio-inspired metaheuristic algorithms have recently been developed to solve the NP-hard influence maximization problem in an efficient and approximate way, being able to find small winning coalitions that maximize the influence spread within an influence graph. In this article, we apply some variations of this solution to find extreme winning and losing coalitions, and thus efficient approximate solutions for the length and the width of influence games. As a case study, we consider two real social networks, one formed by the 58 members of the European Union Council under nice voting rules, and the other formed by the 705 members of the European Parliament, connected by political affinity. Results are promising and show that it is feasible to generate approximate solutions for the length and width parameters of influence games, in reduced solving time, "Funding Statement: F. Riquelme has been partially supported by Fondecyt de Iniciación 11200113, Chile, and by the SEGIB scholarship of Fundación Carolina, Spain; X. Molinero under grants PID2019-104987GB-I00 (JUVOCO); M. Serna under grants PID2020-112581GB-C21 (MOTION) and 2017-SGR-786 (ALBCOM)", Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

The semantics of GQL-like path queries

  • Orejas Valdés, Fernando|||0000-0002-3023-4006
  • Pino Blanco, Elvira|||0000-0003-3376-5096
The success of graph databases (GDBs) has caused the development of several dozens of GDB products by companies like Neo4j, Oracle, Amazon, IBM or SAP. In parallel, several graph query languages have been designed for querying these GDBs, like Cypher for Neo4j, PGQL for Oracle, or GSQL for TigerGraph, which actually are quite similar. This situation has led to propose the creation of a unifying standard for graph query languages. This standard is currently under development, and is called GQL. In a previous paper we defined a logical and an operational semantics for a core language similar to Cypher, showing that the operational semantics is sound and complete with respect to the logical one. However, GQL has gone beyond the expressive power of the above mentioned languages in several senses. Therefore, in the current work, our aim is to redefine the semantics that we gave for Cypher-like languages to a core subset of GQL., This work is partially supported by MCIN/ AEI /10.13039/501100011033 under grant PID2020-112581GB-C21., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Relating real and synthetic social networks through centrality measures

  • Blesa Aguilera, Maria Josep|||0000-0001-8246-9926
  • Popa, Mihail Eduard
  • Serna Iglesias, María José|||0000-0001-9729-8648
We perform here a comparative study on the behaviour of real and synthetic social networks with respect to a selection of nine centrality measures. Some of them are topology based (degree, closeness, betweenness), while others consider the relevance of the actors within the network (Katz, PageRank) or their ability to spread influence through it (Independent Cascade rank, Linear Threshold Rank). We run different experiments on synthetic social networks, with 1K, 10K, and 100K nodes, generated according to the Gaussian Random partition model, the stochastic block model, the LFR benchmark graph model and hyperbolic geometric graphs model. Some real social networks are also considered, with the aim of discovering how do they relate to the synthetic models in terms of centrality. Apart from usual statistical measures, we perform a correlation analysis between all the nine measures. Our results indicate that, in general, the correlation matrices of the different models scale nicely with size. Moreover, the correlation plots distinguish four categories that classify most of the real networks studied here. Those categories have a clear correspondence with particular configurations of the models for synthetic networks., M. Blesa and M. Serna acknowledge support by MICIN/AEI/10.13039/501100011033 under grant PID2020-112581GB-C21 (MOTION). M.E. Popa was funded by the Ministry of Education and Vocational Training (MEFP) with a student grant (Beca de colaboración, call 2020-2021), Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Capítulo o parte de un libro (BookPart)

DP_Kruskal: A concurrent algorithm to maintain dynamically minimum spanning trees

  • Benedí García, Daniel
  • Duch Brown, Amalia|||0000-0003-4371-1286
  • Pasarella Sánchez, Ana Edelmira|||0000-0001-8315-4977
  • Zoltan Torres, Ana Cristina
We provide a working implementation of DP_Kruskal; a parallel, distributed and concurrent adaptation of Kruskal algorithm that keeps the input graph distributed along a pipeline and computes online its minimum spanning tree (or forest) in the Go programming language. We show experimentally that DP_Kruskal is competitive and scales well to a large number of processes. Our experimental study is done for a large class of dynamic random graphs –including several densities and sizes– and some real dynamic graphs., This work has been funded by MCIN/AEI/10.13039/501100011033 under grant PID2020-112581GB-C2., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

A logical approach to graph databases

  • Pino Blanco, Elvira|||0000-0003-3376-5096
  • Orejas Valdés, Fernando|||0000-0002-3023-4006
  • Mylonakis Pascual, Nicolás|||0000-0002-2535-8573
  • Pasarella Sánchez, Ana Edelmira|||0000-0001-8315-4977
Graph databases are now playing an important role because they allow us to overcome some limitations of relational databases. In particular, in graph databases we are interested not only on the data contained but also on its topology. As a consequence, most graph database queries are navigational, asking whether some nodes are connected by edges or paths. Up to now, most foundational work has concentrated on the study of computational models and query languages, analyzing their expressivity, computability, and complexity. However, in our work we address a different kind of foundational work. We are not concerned with expressibility, efficiency or feasibility issues, but with correctness. More precisely, given an algorithm or an implementation for solving queries, how can we be sure that the answers obtained are correct (soundness) and that all possible correct answers are obtained by our implementation (completeness). In this sense, in this paper we first present a core query language, similar to Cypher or G-Core. Then, we define a simple logic whose formulas are precisely the database queries, and whose satisfaction relation defines what is a correct answer. Finally, we define an operational semantics, which could be seen as an abstract implementation of our language, showing that the semantics is correct, i.e. sound and complete with respect to our logic., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Capítulo o parte de un libro (BookPart)

Advanced process discovery techniques

  • Augusto, Adriano
  • Carmona Vargas, Josep|||0000-0001-9656-254X
  • Verbeek, Eric
Given the challenges associated to the process discovery task, more than a hundred research studies addressed the problem over the past two decades. Despite the richness of proposals, many state-of-the-art automated process discovery techniques, especially the oldest ones, struggle to systematically discover accurate and simple process models. In general, when the behavior recorded in the input event log is simple (e.g., exhibiting little parallelism, repetitions, or inclusive choices) or noise free, some basic algorithms such as the alpha miner can output accurate and simple process models. However, as the complexity of the input data increases, the quality of the discovered process models can worsen quickly. Given that oftentimes real-life event logs record very complex and unstructured process behavior containing many repetitions, infrequent traces, and incomplete data, some state-of-the-art techniques turn unreliable and not purposeful. Specifically, they tend to discover process models that either have limited accuracy (i.e., low fitness and/or precision) or are syntactically incorrect. While currently there exists no perfect automated process discovery technique, some are better than others when discovering a process model from event logs recording complex process behavior. In this chapter, we introduce four of such techniques, discussing their underlying approach and algorithmic ideas, reporting their benefits and limitation, and comparing their performance with the algorithms introduced in the previous chapter., This work has been supported by MCIN/AEI funds under grant PID2020-112581GB-C21., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

AntNetAlign: A software package for network alignment

  • Rodríguez i Corominas, Guillem
  • Blesa Aguilera, Maria Josep|||0000-0001-8246-9926
  • Blum, Christian
In this paper we introduce AntNetAlign, an open-source tool (written in C++) that implements an Ant Colony Optimization (ACO) for solving the Network Alignment (NA) problem, a well-known hard optimization problem with important applications in different areas, such as biology or social networks. Specifically, given two input networks, the tool finds an alignment between them (i.e., a mapping between the respective nodes) that optimizes one out of the three main topological measures. Additionally, it can make use of user-defined pairwise similarities between nodes during its construction phase, allowing for the use of more application-dependent information in order to increase its performance. Results show that AntNetAlign outperforms other state-of-the-art algorithms in two out of the three aforementioned topological scores within a reasonable amount of time, and is able to achieve competitive results in the context of larger instances (Rodríguez Corominas et al., 2023). Furthermore, a new version of the algorithm, which makes use of Negative Learning, was able to further improve these results, specially in the EC score (Corominas et al., 2022)., Guillem Rodríguez Corominas gets support from the Department of Research and Universities of the Government of Catalonia by means of an ESF-founded pre-doctoral grant of the Catalan Agency for Management of University and Research Grants (AGAUR, Catalonia, Spain), under ref. number 2022 FI_B 00903. Christian Blum was supported by two grants funded by MCIN/AEI/10.13039/501100011033: AEI, Spain PID2019-104156GB-I00, and TED2021-129319B-I00. Maria J. Blesa acknowledges support from AEI, Spain under grant PID-2020-112581GB-C21 (MOTION) and the Catalan Agency for Management of University and Research Grants (AGAUR , Catalonia, Spain), under grant 2021-SGR-01419 (ALBCOM)., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

On the enumeration of resolute majority rules

  • Freixas Bosch, Josep|||0000-0002-9033-9432
  • Samaniego Vidal, Daniel
This paper considers resolute decision rules in which each voter may vote “yes", “abstain" or vote “no", and the outcome is “yes" or “no". The model we consider is more general than that of simple games since the input admits abstention or indecision, but it is more specialized since it assumes the properties of monotonicity and anonymity. Many subclasses of these resolute decision rules have been studied in the literature from an axiomatic point of view. The purpose of this work is to enumerate these subclasses as a function of the number of voters., This research was partially supported by the Spanish Agencia Estatal de Investigación [PID-2020-112581GB-C21, MOTION] and the Agència de Gestió d’Ajuts Universitaris i de Recerca (AGAUR) of the Government of Catalonia under project 2017 SGR 786 (ALBCOM). We greatly appreciate the comments of two anonymous referees who have contributed to improve the presentation of this work., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

On minimum vertex bisection of random d-regular graphs

  • Díaz Cort, Josep|||0000-0003-4422-0067
  • Yasar Diner, Oznur
  • Serna Iglesias, María José|||0000-0001-9729-8648
  • Serra Albó, Oriol|||0000-0001-8561-4631
Minimum vertex bisection is a graph partitioning problem in which the aim is to find a partition of the vertices into two equal parts that minimizes the number of vertices in one partition set that have a neighbor in the other set. In this work we are interested in providing asymptotically almost surely upper bounds on the minimum vertex bisection of random d-regular graphs, for constant values of d. Our approach is based on analyzing a greedy algorithm by using the differential equation method. In this way, we obtain the first known non-trivial upper bounds for the vertex bisection number in random regular graphs. The numerical approximations of these theoretical bounds are compared with the emprical ones, and with the lower bounds from Kolesnik and Wormald (2014) [30]., J. Díaz and M. Serna were partially supported by the Spanish Agencia Estatal de Investigación under project MOTION, PID2020-112581 GB-C21. O.Y. Diner was partially supported by the Scientific and Technological Research Council Tübitak under project BIDEB 2219-1059B191802095 and by Kadir Has University under project 2018-BAP-08. O. Serra research was supported by the Spanish Agencia Estatal de Investigación under project CONTREWA, PID2020-113082 GB-I00., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Negative learning ant colony optimization for network alignment

  • Rodríguez Corominas, Guillem
  • Blum, Christian
  • Blesa Aguilera, Maria Josep|||0000-0001-8246-9926
The Network Alignment problem is a hard Combinatorial Optimization problem with a wide range of applications, especially in computational biology. Given two (or more) networks, the goal is to find a mapping between their respective nodes that preserves the topological and functional structure of the networks. In this work we extend a novel ant colony optimization approach for network alignment by adding a recently proposed Negative Learning mechanism. In particular, information for Negative Learning is obtained by solving sub-instances of the tackled problem instances at each iteration by means of an Integer Linear Programming solver. The results show that the proposed algorithm not only outperforms the standard ant colony optimization approach but also current state-of-the-art methods from the literature., M. Blesa acknowledges support by AGAUR (GENCAT) under grant 2017-SGR-786 (ALBCOM). Moreover, the authors acknowledge support by MCIN/AEI/10.13039/501100011033 under grant PID2020-112581GB-C21 (MOTION) and grant PID2019-104156GB-I00 (CISUSTAIN)., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Tight bounds for an accelerated k-means++ algorithm

  • Rodríguez i Corominas, Guillem
  • Blesa Aguilera, Maria Josep|||0000-0001-8246-9926
  • Blum, Christian
In this paper, we improve a recently introduced accelerated k-means++ algorithm by proposing a dynamic method for calculating bounds during its execution. This approach produces high-quality bounds without requiring a full iteration over the dataset, using the Triangle Inequality and the norm of the points for efficient computation. We propose three evaluation metrics to assess the quality of the calculated bounds and analyze their behavior across a diverse dataset. Results show that this dynamic method outperforms the traditional approach of initializing bounds at the end of the process, before the execution of the k-means algorithm., The research presented in this paper was supported by grant 2022 FI_B 00903 funded by the AGAUR; grant PID-2020-112581GB-C21 (MOTION) funded by the AEI; grants TED2021-129319B-I00 and PID2022-136787NB-I00 funded by MCIN/AEI/10.13039/501100011033; and project MMT24-IIIA-02 funded by Red.es, Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

A proposal for an Educational Well-Being Index (EWI) for undergraduate course design

  • Blesa Aguilera, Maria Josep|||0000-0001-8246-9926
  • Duch Brown, Amalia|||0000-0003-4371-1286
  • Gabarró Vallès, Joaquim|||0000-0003-3771-2813
  • Serna Iglesias, María José|||0000-0001-9729-8648
Every day it is more common to hear around us about the publication of studies, surveys or statistical results about the well-being of people, workers, women in a given country. Indeed, as university professors, our work cannot be independent of the level of well-being of our students. So, in this work, we propose a methodology to asses the students well-being inside a course implementation by what we call the educational well-being index (EWI). We start with a survey that gathers those factors that computing courses’ students at our university –of two different levels and majors– consider most important. Our second step is the evaluation –by a group of teachers– of the presence of those factors in different educational models of implementation of the courses. We use principal component analysis to extract, from the student data, the valuations that they expressed in the survey: the principal component of their own measurements on well-being. We work only with the coefficients of the first dimension of the principal component. The third step is a (subjective) valuation of the topics addressed in the survey when considering a particular educational model. Finally, we gather everything together to obtain a well-being index of an educational model that allows their comparison. Besides the methodology, we present and analyze the values obtained from our case study., Supported by MCIN/AEI/10.13039/501100011033 under grant PID2020-112581GB-C21 (MOTION)., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Forward and backward linear threshold ranks

  • Blesa Aguilera, Maria Josep|||0000-0001-8246-9926
  • García Rodríguez, Pau
  • Serna Iglesias, María José|||0000-0001-9729-8648
We propose the FwLTR and BwLTR, two new centrality measures based on the Linear Threshold model. In contrast to the Linear Threshold rank (LTR), these measures differentiate between the incoming and the outgoing neighborhoods of the activation set that initiates the spreading process. Their rankings are distinguishable from the rest of the centrality measures considered traditionally. However, LTR and BwLTR behave quite similarly, while FwLTR is clearly different., Supported by AEI under grant PID-2020-112581GB-C21 (MOTION) and AGAUR under grant 2017-SGR-786 (ALBCOM)., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Median and hybrid median K-dimensional trees

  • Duch Brown, Amalia|||0000-0003-4371-1286
  • Martínez Parra, Conrado|||0000-0003-1302-9067
  • Pons, Mercè
  • Roura Ferret, Salvador|||0000-0003-4394-5939
We consider here two new variants of K-dimensional binary search trees (K-d trees): median K-d trees and hybrid-median K-d trees. These two kinds of trees are designed with the aim to get a tree as balanced as possible. This goal is attained by heuristics that choose for each node of the K-d tree the appropriate coordinate to discriminate. In the case of median K-d trees, the chosen dimension to discriminate at each node is the one whose point value at that node is the most centered one. In hybrid-median K-d trees, the heuristic is similar except that it should be followed in a cyclic way, meaning that, at every path of the tree, no dimension can be re-selected to discriminate unless all the other dimensions have already been selected. We study the expected internal path length (IPL) and the expected cost of random partial match (PM) searches in both variants of K-d trees. For both variants, we prove that the expected IPL is of the form cK⋅nlog2n+lower order terms , and the expected cost of PM is of the form Θ(nα) with α=α(s,K) . We give the explicit equations satisfied by the constants cK and the exponents α which we can then numerically solve. Moreover, we prove that as K→∞ the trees in both variants tend to be perfectly balanced (cK→1 ) and we also show that α→log2(2−s/K) for median K -d trees when K→∞ . In the case of hybrid median K -d trees we conjecture that α→1−s/K , when K→∞ , which would be optimal., This work has been supported by funds from the MOTION Project (Project PID2020-112581GB-C21) of the Spanish Ministery of Science & Innovation MCIN/AEI/10.13039/501100011033., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

How can graph databases and reasoning be combined and integrated?

  • Pasarella Sánchez, Ana Edelmira|||0000-0001-8315-4977
Nowadays the graph data model has been accepted as one of the most suitable data models to formalize relationships among entities of many domains. Deductive databases based on the Datalog language have been used to deduce new information from large amounts of data. Most of the attempts to combine logic and graph databases are based on translating knowledge in graph databases into Datalog and then use its inference engine. We aim to open the discussion about combining graph databases and a graph-oriented logic to define «native» deductive graph databases. This is, graph databases equipped with an inference mechanism based on graph based logic. To be concrete, we plan to use the recently introduced graph navigational logic., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Capítulo o parte de un libro (BookPart)

A probabilistic model revealing shortcomings in Lua’s hybrid tables

  • Martínez Parra, Conrado|||0000-0003-1302-9067
  • Nicaud, Cyril
  • Rotondo, Pablo
Lua (Ierusalimschy et al., 1996) is a well-known scripting language, popular among many programmers, most notably in the gaming industry. Remarkably, the only data-structuring mechanism in Lua, is an associative array called a table. With Lua 5.0, the reference implementation of Lua introduced hybrid tables to implement tables using both a hash table and a dynamically growing array combined together: the values associated with integer keys are stored in the array part, when suitable. All this is transparent to the user, which has a unique simple interface to handle tables. In this paper we carry out a theoretical analysis of the performance of Lua ’s tables, by considering various worst-case and probabilistic scenarios. In particular, we uncover some problematic situations for the simple probabilistic model where we add a new key with some fixed probability p>1/2 and delete a key with probability 1−p: the cost of performing T such operations is proved to be Ω(TlogT) with high probability, instead of linear in T., The work of the first author has been supported by funds from project MOTION (Project PID2020-112581GB-C21) of the Spanish Ministry of Science & Innovation MCIN/AEI/10.13039/501100011033., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

SoftBinReduce: data reduction for color quantization through soft binning

  • Rodríguez i Corominas, Guillem
  • Blesa Aguilera, Maria Josep|||0000-0001-8246-9926
  • Blum, Christian
In this paper, we propose SoftBinReduce, a data reduction method for Color Quantization. Our approach consists of four main steps: (1) identifying representatives in each channel, (2) generating three-dimensional bins, (3) distributing pixel values using a soft binning technique, and (4) repositioning the resulting bins. Additionally, we introduce an adapted Sort-Means algorithm for the Pixel Mapping phase, providing a strong initial guess. We conduct an extensive experimental evaluation primarily using the CQ100 dataset, but also the older Kodak and USC-SIPI datasets. We compare our method to two well-known data reduction techniques from the literature: pseudo-random and quasi-random sampling. The results demonstrate that our method outperforms both in terms of NMSE error versus the achieved speedup, particularly when the data is significantly reduced and with a higher number of colors in the generated palette. Moreover, an ablation study shows that all components of our method are necessary for producing high-quality results., Open Access funding provided thanks to the CRUE-CSIC agreement with Springer Nature. Guillem Rodríguez Corominas acknowledges support from the Department of Research and Universities of the Government of Catalonia by means of an ESF-founded pre-doctoral grant of the Catalan Agency for Management of University and Research Grants (AGAUR), under ref. number 2022 FI_B 00903. Maria J. Blesa acknowledges support from AEI under MICINN grant PID-2020-112581GB-C21 (MOTION). Christian Blum was supported by two grants funded by MCIN/ AEI/10.13039/501100011033: TED2021-129319B-I00 and PID2022-136787NB-I00., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Mathematical models to describe fixation disparity curves

  • Argilés Sans, Marc|||0000-0001-5474-9832
  • Molinero Albareda, Xavier|||0000-0002-5203-4347
Purpose This study developed mathematical models to describe the four classical types of Fixation Disparity Curves (FDCs), addressing the limitations of existing generalised polynomial fits. These models provide an objective framework for analysing FDCs, with the goal of improving the diagnosis and management of binocular vision disorders. Methods The study was conducted in two phases. In the first phase, elementary mathematical functions were identified for each type of FDC: a polynomial function for Type I, an exponential function for Types II and III and a trigonometric function for Type IV. The function parameters were optimised using the least squares method in MATLAB. In the second phase, the models were validated using experimental data from 20 participants to ensure representation of all FDC types. The fixation disparity was measured using the Wesson card over a range of seven vergence demands. Results The proposed models accurately represented the shape and characteristics of each FDC, achieving 85% classification accuracy across all four types. Agreement between the model and subjective classification by optometrists was 75%. A statistically significant difference was observed in slope calculations between types using the developed model (p¿=¿0.002), but not with a general polynomial fit (p¿=¿0.36). Conclusions The newly developed models improve the precision and reliability of FDC analysis, thereby reducing subjective bias. These models have potential applications in both clinical and research settings for more accurate binocular vision assessments., This publication is part of the project PID2023-146101OB-I00. X. Molinero was partially supported by the Spanish Agencia Estatal de Investigación & Innovation AE I/10.13039/501100011033 (Project PID2020-112581GB-C21 MOTION)., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Rainbow connectivity of multilayered random geometric graphs

  • Díaz Cort, Josep|||0000-0003-4422-0067
  • Diner, Oznur Y.
  • Serra Albó, Oriol|||0000-0001-8561-4631
  • Serna Iglesias, María José|||0000-0001-9729-8648
An edge-colored multigraph G is rainbow connected if every pair of vertices is joined by at least one rainbow path, i.e., a path where no two edges are of the same color. In the context of multilayered networks, we introduce the notion of multilayered random geometric graphs, from h = 2 independent random geometric graphs G(n,r) on the unit square. We define an edge-coloring by coloring the edges according to the copy of G(n,r) they belong to and study the rainbow connectivity of the resulting edge-colored multigraph. We show that r(n) = lnn nh-1 1/2h , is a threshold of the radius for the property of being rainbow connected. This complements the known analogous results for the multilayered graphs defined on the Erdos–Rényi random model., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Mathematical models to analyze Lua hybrid tables

  • Martínez Parra, Conrado|||0000-0003-1302-9067
  • Nicaud, Cyril
  • Rotondo, Pablo
Lua (Ierusalimschy et al., 1996) is a well-known scripting language, popular among many programmers, most notably in the gaming industry. Remarkably, the only data-structuring mechanism in Lua is given by associative arrays, called tables. With Lua 5.0, the reference implementation of Lua introduced hybrid tables to implement tables using both a hashmap and a dynamically growing array combined together: the values associated with integer keys are stored in the array part, when suitable, everything else is stored in the hashmap. All this is transparent to the user, who gets a unique simple interface to handle tables. In this paper we carry out a theoretical analysis of the performance of Lua's tables, by considering various worst-case and probabilistic scenarios. In particular, we uncover some problematic situations for the simple probabilistic model where we add a new key with some fixed probability p > 1/2 and delete a key with probability 1-p: the cost of performing T such operations is proved to be O(TlogT) with high probability, where linear complexity would be assumed for such data structure. If there is no deletion, we prove that the tables behave better overall. In particular, we establish that inserting the T integers from 1 to T in a random order is done in an essentially linear time., The work of the first author has been supported by funds from project MOTION (Project PID2020-112581GB-C21) of the Spanish Ministry of Science & Innovation MCIN/AEI/10.13039/501100011033., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Reconstruction of random geometric graphs: breaking the Ω(r) distortion barrier

  • Dani, Varsha
  • Díaz Cort, Josep|||0000-0003-4422-0067
  • Hayes, Thomas P.
  • Moore, Cristopher
Embedding graphs in a geographical or latent space, i.e. inferring locations for vertices in Euclidean space or on a smooth manifold or submanifold, is a common task in network analysis, statistical inference, and graph visualization. We consider the classic model of random geometric graphs where n points are scattered uniformly in a square of area n, and two points have an edge between them if and only if their Euclidean distance is less than r. The reconstruction problem then consists of inferring the vertex positions, up to the symmetries of the square, given only the adjacency matrix of the resulting graph. We give an algorithm that, if r = n α for any 0 < α < 1/2, with high probability reconstructs the vertex positions with a maximum error of O(n β ) where β = 1/2−(4/3)α, until α ≥ 3/8 where β = 0 and the error becomes O( √ log n). This improves over earlier results, which were unable to reconstruct with error less than r. Our method estimates Euclidean distances using a hybrid of graph distances and short-range estimates based on the number of common neighbors. We extend our results to the surface of the sphere in R 3 and to hypercubes in any constant fixed dimension., Josep Díaz: partially supported by PID-2020-112581GB-C21 (MOTION). Cristopher Moore: partially supported by National Science Foundation grant IIS-1838251., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

The multicolored graph realization problem

  • Díaz Cort, Josep|||0000-0003-4422-0067
  • Yasar Diner, Oznur
  • Serna Iglesias, María José|||0000-0001-9729-8648
  • Serra Albó, Oriol|||0000-0001-8561-4631
We introduce the multicolored graph realization problem (MGR). The input to this problem is a colored graph (G, φ), i.e., a graph G together with a coloring φ on its vertices. We associate each colored graph (G, φ) with a cluster graph (Gφ ) in which, after collapsing all vertices with the same color to a node, we remove multiple edges and self-loops. A set of vertices S is multicolored when S has exactly one vertex from each color class. The MGR problem is to decide whether there is a multicolored set S so that, after identifying each vertex in S with its color class, G[S] coincides with Gφ . The MGR problem is related to the well-known class of generalized network problems, most of which are NP-hard, like the generalized Minimum Spanning Tree problem. The MGR is a generalization of the multicolored clique problem, which is known to be W [1]-hard when parameterized by the number of colors. Thus, MGR remains W [1]-hard, when parameterized by the size of the cluster graph. These results imply that the MGR problem is W [1]-hard when parameterized by any graph parameter on Gφ , among which lies treewidth. Consequently, we look at the instances of the problem in which both the number of color classes and the treewidth of Gφ are unbounded. We consider three natural such graph classes: chordal graphs, convex bipartite graphs and 2-dimensional grid graphs. We show that MGR is NP-complete when Gφ is either chordal, biconvex bipartite, complete bipartite or a 2-dimensional grid. Our reductions show that the problem remains hard even when the maximum number of vertices in a color class is 3. In the case of the grid, the hardness holds even for graphs with bounded degree. We provide a complexity dichotomy with respect to cluster size ., J. Díaz and M. Serna are partially supported by funds from the Spanish Agencia Estatal de Investigación under grant PID2020-112581GB-C21 (MOTION), and from AGAUR under grant 2017-SGR-786 (ALBCOM). Ö. Y. Diner is partially supported by the Scientific and Technological Research Council Tübitak under project BIDEB 2219-1059B191802095 and by Kadir Has University under project 2018-BAP-08. O. Serra is supported by the Spanish Agencia Estatal de Investigación under grant PID2020-113082GB-I00., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

A stream processing-based algorithm for maintaining minimum spanning forests of evolving graphs

  • Benedí García, Daniel
  • Duch Brown, Amalia|||0000-0003-4371-1286
  • Pasarella Sánchez, Ana Edelmira|||0000-0001-8315-4977
In this work we introduce a concurrent/parallel adaptation of Kruskal algorithm based on the dynamic pipeline approach. This is, the input (undirected) graph is given by a stream of weighted edges and it is dynamically created and maintained in a distributed way along a pipeline of stateful stages. To be concrete, firstly an initial graph is created and then, whenever the graph evolves because of edges are added, removed or updated, the minimum spanning tree (forest) according to the current graph can be computed and output immediately. Moreover, we provide a working implementation in the Go programming language. Go is suitable to dynamic pipelines’ implementations thanks to its communication channels and co-routines. We show experimentally that our algorithm scales well to a large number of processes and that it is competitive against the classic sequential Kruskal algorithm and a well known parallelized version of the Kruskal algorithm. Our experimental study is done for a large class of dynamic random graphs –including several densities and sizes– and some real dynamic graphs., This work has been funded by MCIN/AEI/10.13039/501100011033 under grant PID2020-112581GB-C21., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Weightedness measures from inequality systems

  • Albareda Sambola, Maria|||0000-0002-7666-6218
  • Molinero Albareda, Xavier|||0000-0002-5203-4347
  • Roura Ferret, Salvador|||0000-0003-4394-5939
A simple game is a cooperative game where some coalitions among players or voters became the (monotonic) set of winning coalitions, and the other ones form the set of losing coalitions. It is well-known that weighted voting games form a strict subclass of simple games, where each player has a voting weight so that a coalition wins if and only if the sum of weights of their members exceeds a given quota, otherwise it loses. This work studies how far away a simple game is for being representable as a weighted voting game, which allows for a more compact representation. There are several measures that determine the weightedness of a simple game, such as the dimension, the trade-robustness, the critical threshold value associated with the a-roughly weightedness property, etc. In this work we propose some new weightedness measures, all based on linear programming. In general terms, for a given simple game, a linear program is used to identify its weightedness: (i) the ¿-roughly value (µe ), (ii) the Z+ -roughly value (µZ+ ), (iii) the ¿-roughly value (µ¿ ), and (iv) the outlier value (¿M ). We show a close relation between the known critical threshold value of weightedness and the new measure µ¿ . Finally, we also present an exhaustive comparison of weightedness measures for simple games with up to six players., M. Albareda-Sambola was funded by MCIN/AEI/10.13039/501100011033/FEDER-EU project PID2022-139219OB-I00 and RED2022-134149-T. X. Molinero was partially supported by MCIN/AEI/10.13039/501100011033 under grant PID2020-112581GB-C21 (MOTION). X. Molinero and S. Roura were also partially supported by the Catalan government [2021 SGR 01419 ALBCOM]., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Nash’s bargaining problem and the scale-invariant Hirsch citation index

  • Freixas Bosch, Josep|||0000-0002-9033-9432
  • Hoerl, Roger
  • Zwicker, William
A number of citation indices have been proposed for measuring and ranking the research publication records of scholars. Some of the best known indices, such as those proposed by Hirsch and Woeginger, are designed to reward most highly those records that strike some balance between productivity (number of papers published) and impact (frequency with which those papers are cited). A large number of rarely cited publications will not score well, nor will a very small number of heavily cited papers. We discuss three new citation indices, one of which was independently proposed in Fenner et al. (PLOS ONE 13(7): e0200098, 2018). Each rests on the notion of scale invariance, fundamental to John Nash’s solution of the two-person bargaining problem. Our main focus is on one of these—a scale-invariant version of the Hirsch index. We argue that it has advantages over the original; it produces fairer rankings within subdisciplines, is more decisive (discriminates more finely, yielding fewer ties) and more dynamic (growing over time via more frequent, smaller increments), and exhibits enhanced centrality and tail balancedness. Simulations suggest that scale invariance improves robustness under Poisson noise, with increased decisiveness having no cost in terms of the number of “accidental” reversals, wherein random irregularities cause researcher A to receive a lower index value than B, although A’s productivity and impact are both slightly higher than B’s. Moreover, we provide an axiomatic characterization of the scale-invariant Hirsch index, via axioms that bear a close relationship, in discrete analogue, to those used by Nash (Econometrica 18(2):155–162, 1950). This argues for the mathematical naturality of the new index., The first author’s research was partially supported by MCIN/AEI/10.13039/501100011033 under grant PID2020-112581GB-C21 (MOTION). The third author’s work was partially supported by the CY Initiative of Excellence (grant “Investissements d’Avenir” ANR-16-IDEX-0008) and was developed partly during the author’s stay at CY Advanced Studies. We thank Denis Bouyssou for his informative comments, and the two referees for many helpful suggestions, all of which improved the manuscript., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Partial match queries in quad-K-d trees

  • Duch Brown, Amalia|||0000-0003-4371-1286
  • Martínez Parra, Conrado|||0000-0003-1302-9067
Quad-K-d trees [Bereckzy et al., 2014] are a generalization of several well-known hierarchical Kdimensional data structures. They were introduced to provide a unified framework for the analysis of associative queries and to investigate the trade-offs between the cost of different operations and the memory needs (each node of a quad-K-d tree has arity 2 m for some m, 1 ≤ m ≤ K). Indeed, we consider here partial match – one of the fundamental associative queries – for several families of quad-K-d trees including, among others, relaxed K-d trees and quadtrees. In particular, we prove that the expected cost of a random partial match Pˆn that has s out of K specified coordinates in a random quad-K-d tree of size n is Pˆn ∼ β · n α where α and β are constants given in terms of K and s as well as additional parameters that characterize the specific family of quad-K-d trees under consideration. Additionally, we derive a precise asymptotic estimate for the main order term of Pn,q – the expected cost of a fixed partial match in a random quad-K-d tree of size n. The techniques and procedures used to derive the mentioned costs extend those already successfully applied to derive analogous results in quadtrees and relaxed K-d trees; our results show that the previous results are just particular cases, and states the validity of the conjecture made in [Duch et al., 2016] to a wider variety of multidimensional data structures., This work has been supported by funds from the MOTION Project (Project PID2020-112581GB-C21) of the Spanish Ministery of Science and Innovation MCIN/AEI/10.13039/501100011033., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

The metric dimension of sparse random graphs

  • Díaz Cort, Josep|||0000-0003-4422-0067
  • Hartle, Harrison
  • Moore, Cristopher
In 2013, Bollobás, Mitsche, and Pralat gave upper and lower bounds for the likely metric dimension of random Erdos-Rényi graphs G(n,p) for a large range of expected degrees. However, their results only apply when d=pn=omega(log^5 n), leaving open sparser random graphs with d=O(log^5 n) or d=o(log^5n). Here we provide upper and lower bounds on the likely metric dimension of G(n,p) in a range of d starting just above the connectivity transition, i.e., where d=c log n for some constant c>1, up to d=O(log^5 n). Our lower bound technique is based on an entropic argument which is weaker but more general than the use of Suen's inequality by Bollobás, Mitsche, and Pralat, whereas our upper bound is similar to theirs., This work was supported by the Spanish Ministry of Science and Innovation, projectPID2020-112581GB-C21 MOTION (J. Díaz), the Santa Fe Institute (H. Hartle, C. Moore),and the Robert Wood Johnson Foundation (C. Moore)., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Improved reconstruction of random geometric graphs

  • Dani, Varsha
  • Díaz Cort, Josep|||0000-0003-4422-0067
  • Hayes, Thomas P.
  • Moore, Cristopher
Embedding graphs in a geographical or latent space, i.e. inferring locations for vertices in Euclidean space or on a smooth manifold or submanifold, is a common task in network analysis, statistical inference, and graph visualization. We consider the classic model of random geometric graphs where n points are scattered uniformly in a square of area n, and two points have an edge between them if and only if their Euclidean distance is less than r. The reconstruction problem then consists of T A inferring the vertex positions, up to the symmetries of the square, given only the adjacency matrix of the resulting graph. We give an algorithm that, if r = nα for α > 0, with high probability reconstructs the vertex positions with a maximum error of O(nβ) where β = 1/2 − (4/3)α, until α ≥3/8 where β =0 and the error becomes O(√ log n). This improves over earlier results, which E were unable to reconstruct with error less than r. Our method estimates Euclidean distances using a hybrid of graph distances and short-range estimates based on the number of common neighbors. We extend our results to the surface of the sphere in R3 and to hypercubes in any constant dimension., Josep Díaz: Partially supported by PID-2020-112581GB-C21 (MOTION). Thomas P. Hayes: Partially supported by NSF grant CCF-1150281. Cristopher Moore: Partially supported by NSF grant IIS-1838251., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Small language models for less-resourced languages in a real-world scenario: The case for Catalan

  • Saurí Colomer, Roser
  • Sànchez-Ferreres, Josep|||0000-0002-7204-4307
  • Padró, Lluís|||0000-0003-4738-5019
  • Carmona Vargas, Josep|||0000-0001-9656-254X
Small Language Models (SLMs), typically ranging from a few million to 10–15 billion parameters, offer a promising solution towards constraints imposed by platform size–particularly mobile and IoT devices–and by the requirements of many organizations such as SMEs, which need solutions that ensure data privacy while remaining cost-effective. Their compactness and efficiency provide digital sovereignty and flexibility, though with more limited general-purpose capabilities. This makes them especially sensitive when working with underrepresented languages, such as Catalan, due to interference from majority languages that can increase bias risk. This paper evaluates state-of-the-art SLMs in a real-world Catalan use case: an AI assistant for older adults, assessing both user interactions and structured function call generation. Our work, which contributes to the FREC initiative for deploying a connected SLM-based infrastructure under the Model Context Protocol, demonstrates that some SLMs are able to deliver high-quality performance even in resource-constrained, linguistically minority environments., This piece of work has been supported by MCIN/AEI/10.13039/501100011033 under grant PID2020-112581GB-C21 (MOTION). Also, by the European Union – NextGenerationEU, Spain’s Recovery, Transformation and Resilience Plan (RRP), in collaboration with the Catalan government (Generalitat de Catalunya), under grant SDC007/25/000055., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Capítulo o parte de un libro (BookPart)

LotterySampling: A randomized algorithm for the Heavy Hitters and Top-k problems in data streams

  • Martínez Parra, Conrado|||0000-0003-1302-9067
  • Solera Pardo, Gonzalo
We propose a new randomized count-based algorithm to solve the Heavy Hitters and Top-k problems in data streams. This algorithm, called LotterySampling, uses the intuitive concept of “lottery tickets”, to decide which elements to sample. We prove that LotterySampling is inside the (δ,ϵ)-deficient framework for the Heavy Hitters problem and that it has a similar performance to the well known StickySampling algorithm, although they are very different in nature. More importantly, we define a similar (δ,ϵ)-deficient framework for the harder Top-k problem and we prove that LotterySampling is inside it. Hence, LotterySampling can be used, without any previous assumption of the data distribution, as a probabilistic approximation scheme to find the k most frequent elements and to approximate the frequencies of the reported elements by a factor of 1−ϵ . To the best of our knowledge, this is the first algorithm that gives theoretical guarantees for the Top-k problem for unknown and arbitrary streams, which is the most important contribution of this paper. Its memory usage is adaptive to the distribution of the stream, and it will increase or decrease depending on whether the stream becomes less or more skewed. More precisely, the sample size depends, at any given moment, on the unknown kth highest frequency but it is independent of the length of the stream and of the number of distinct elements. The user just needs to provide two parameters that determine the quality of the answers, independently of the stream. We compare LotterySampling with other existing probabilistic and deterministic algorithms showing its strengths and weaknesses., This work has been supported by funds from the MOTION Project (Project PID2020-112581GB-C21) of the Spanish Ministry of Science & Innovation MCIN/AEI/10.13039/501100011033, while the second author was a postgraduate student at Universitat Politècnica de Catalunya., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Theoretical and empirical analysis of cost-function merging for implicit hitting set WCSP solving

  • Larrosa Bondia, Francisco Javier|||0000-0002-8322-0505
  • Martínez Parra, Conrado|||0000-0003-1302-9067
  • Rollón Rico, Emma|||0000-0001-8021-9464
The Implicit Hitting Set (HS) approach has shown very effective for MaxSAT solving. However, only preliminary promising results have been obtained for the very similar Weighted CSP framework. In this paper we contribute towards both a better theoretical understanding of the HS approach and a more effective HS-based solvers for WCSP. First, we bound the minimum number of iterations of HS thanks to what we call distinguished cores. Then, we show a source of inefficiency by introducing two simple problems where HS is unfeasible. Next, we propose two reformulation methods that merge cost-functions to overcome the problem. We provide a theoretical analysis that quantifies the magnitude of the improvement of each method with respect to the number of iterations of the algorithm. In particular, we show that the reformulations can bring an exponential number of iterations down to a constant number in our working examples. Finally, we complement our theoretical analysis with two sets of experiments. First, we show that our results are aligned with real executions. Second, and most importantly, we conduct experiments on typical benchmark problems and show that cost-function merging may be heuristically applied and it may accelerate HS algorithms by several orders of magnitude. In some cases, it even outperforms state-of-the-art solvers., The work of Javier Larrosa and Emma Rollon was supported by grant PID2021-122830OB-C43, funded by MCIN/AEI/ 10.13039/501100011033 and by “ERDF: A way of making Europe”. The work of Conrado Martínez was supported by grant PID2020-112581GB-C21 (MOTION Project), funded by MCIN/AEI/10.13039/501100011033., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Capítulo o parte de un libro (BookPart)

Conformance checking: foundations, milestones and challenges

  • Carmona Vargas, Josep|||0000-0001-9656-254X
  • Dongen, Boudewijn F. van
  • Weidlich, Matthias
By relating observed and modelled behaviour, conformance checking unleashes the full power of process mining. Techniques from this discipline enable the analysis of the quality of a process model discovered from event data, the identification of potential deviations, and the projection of real traces onto process models. This way, the insights gained from the available event data can be transferred to a richer conceptual level, amenable for a human interpretation. The aforementioned functionalities are grounded on the use of conformance checking artefacts that explicit the relation between observed and modelled behaviour. This chapter describes these artefacts, and builds upon them to gain evidence-based insights on the processes of an organization. Moreover, we overview the applications of conformance checking and propose a general framework that incorporates these applications. Finally, milestones and challenges of the field are outlined., This work has been supported by MCIN/AEI funds under grant PID2020-112581GB-C21., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Resource-guided FPGA floorplanning via quad-tree-based NLP optimization

  • Chen, Ze|||0000-0003-4111-6715
  • Cortadella, Jordi|||0000-0001-8114-250X
Field-programmable gate arrays (FPGAs) are widely adopted as accelerators for compute-intensive applications. In modern FPGA flows, floorplanning provides coarse-grained region constraints, but commercial tools offer no automatic support, requiring designers to manually define partition regions that substantially impact placement and routing. This paper presents a fully automatic framework that generates resource-guided floorplanning constraints to improve the clock frequency of FPGA designs. The framework employs a divide-and-conquer strategy with nonlinear optimization for resource-aware region assignment, exploiting FPGA heterogeneity in a device-agnostic manner and producing constraints that integrate into commercial toolflows. The framework has been integrated into Vivado and tested with nine benchmarks and two platforms, improving the maximum clock frequency by 11.4% and 5.8%, respectively, and yielding an additional 4.1% gain with timing-optimization strategies without significant congestion overhead., This work has been supported by funds from the Spanish Agencia Estatal de Investigación under grant PID2020-112581GB-C21 (MOTION), and by the China Scholarship Council (CSC)., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

A computational framework based on the dynamic pipeline approach

  • Pasarella Sánchez, Ana Edelmira|||0000-0001-8315-4977
  • Vidal Serodio, Maria Esther
  • Zoltán, Cristina
  • Royo Sales, Juan Pablo
© 2024 The Authors. Published by Elsevier Inc, Stream processing has inspired new computational approaches to facilitate effectiveness and efficiency. One such approach is the dynamic pipeline, which serves as a powerful computational model for stream processing. It is particularly well suited for solving problems that require incremental generation of results, making it an approach for scenarios where real-time analysis and responsiveness are critical. This paper aims to address a family of problems using the Dynamic Pipeline approach, and as a first step, we provide a comprehensive characterization of this problem family. In addition, we present the definition of a Dynamic Pipeline framework. To demonstrate the practicality of this framework, we present a proof of concept through its implementation and perform an empirical performance study. To this end, we focus on solving the problem of enumerating or listing the weakly connected components of a graph within the proposed framework. We provide two implementations of this algorithm to demonstrate the computational power and continuous behavior of the Dynamic Pipeline framework. The first implementation serves as a baseline for our experiments, representing an ad hoc solution based on the Dynamic Pipeline approach. In contrast, the second implementation is built on top of the developed framework. The observed results strongly support the suitability and effectiveness of the Dynamic Pipeline framework for implementing graph stream processing problems, especially those where continuous and real-time result generation is essential., This work has been partially supported by MCIN/ AEI /10.13039/501100011033 under grant PID2020-112581GB-C21 and by the Leibniz Association Germany, “Leibniz Best Minds: Programme for Women Professors”, project TrustKG-Transforming Data in Trustable Insights; Grant P99/2020., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Affirmative sampling: theory and applications

  • Lumbroso, Jérémie
  • Martínez Parra, Conrado|||0000-0003-1302-9067
Affirmative Sampling is a practical and efficient novel algorithm to obtain random samples of distinct elements from a data stream. Its most salient feature is that the size S of the sample will, on expectation, grow with the (unknown) number n of distinct elements in the data stream. As any distinct element has the same probability to be sampled, and the sample size is greater when the “diversity” (the number of distinct elements) is greater, the samples that Affirmative Sampling delivers are more representative than those produced by any scheme where the sample size is fixed a priori - hence its name. Our algorithm is straightforward to implement, and several implementations already exist., This work has been supported by funds from the MOTION Project (Project PID2020-112581GB-C21) of the Spanish Ministry of Science & Innovation MCIN/AEI/10.13039/501100011033, and by Princeton University, and its Department of Computer Science., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

FastKPP: An exact accelerated k-means++ algorithm

  • Rodríguez i Corominas, Guillem
  • Blesa Aguilera, Maria Josep|||0000-0001-8246-9926
  • Blum, Christian
In this paper, we present FastKpp, a C++ implementation of an exact accelerated 𝑘-means++ algorithm using two geometry-aware filters: one based on the Triangle Inequality (TIE) and another based on point norms. Both provably preserve the original 𝐷2 sampling distribution while avoiding redundant distance computations. The library provides a header-only API, a command-line tool, and a fully reproducible capsule. Experiments show substantial reductions in distance computations and speedups that increase with k (with typical median between 2 and 8). Furthermore, FastKpp outperforms other state-of-the-art exact acceleration techniques. Results are reproducible via the public GitHub repository and Code Ocean capsule., This work was supported in part by the Department of Research and Universities of the Government of Catalonia by means of an European Social Fund (ESF)-Founded Pre-Doctoral Grant of the Catalan Agency for Management of University and Research Grants (AGAUR) under Grant 2022 FI_B 00903, in part by the Agencia Estatal de Investigación (AEI) under grants PID-2020-112581GB-C21 (MOTION) and PID2022-136787NB-I00 (ACISUD), and in part by the European Commission–NextGenerationEU, through Momentum CSIC Programme: Develop Your Digital Talent, under Project MMT24-IIIA-02., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

The analysis of partial match queries in random multidimensional trees: A selected survey

  • Duch Brown, Amalia|||0000-0003-4371-1286
  • Hwang, Hsien-Kuei
  • Martínez Parra, Conrado|||0000-0003-1302-9067
  • Neininger, Ralph
We analyze the probabilistic performance of partial match queries in random multidimensional search trees, using k-d trees (and their variants) and quadtrees, as primary examples. A partial match query aims to retrieve all points from a tree that match a given query point on a predetermined subset of coordinates. As one of the most basic associative searches, its analysis is foundational for evaluating more complex queries. This selection of data structures allows us to demonstrate common analytical techniques and offer a historical perspective on the field., The work of Amalia Duch and Conrado Martínez has been supported by funds from the MOTION Project (Project PID2020-112581GB-C21) of the Spanish Ministry of Science and Innovation MCIN/AEI/10.13039/501100011033., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Take the challenge: compute the CO2e emissions of your programming course

  • Gabarró Vallès, Joaquim|||0000-0003-3771-2813
  • Blesa Aguilera, Maria Josep|||0000-0001-8246-9926
  • Duch Brown, Amalia|||0000-0003-4371-1286
  • Serna Iglesias, María José|||0000-0001-9729-8648
Sustainability constraints ask for quick and drastic changes in the ways to teach at university. Here we study the amount of carbon emissions of lecturing a first course in programming. In addition to fix costs estimations, our study relies on a pool on student mobility patterns at our university. We estimate, per campus and level of presentiality, the amount of CO2e emissions of the course. Our results show that the main contributed cost of the course is not always due to transportation. Indeed, the difference in emissions between virtual and face-to-face is not huge and in some cases face-to-face is even better. This offers a discussion about the convenience of replacing face-to-face by virtual teaching through minimizing transportation emissions. We claim that the former can be made CO2e competitive by disseminating the lectures across the city avoiding the use of costly traveling means., This work was partially supported by the Spanish Agencia Estatal de Investigación, under grant PID2020-112581GB-C21 (MOTION)., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Area-driven Boolean bi-decomposition by function approximation

  • Bernasconi, Anna
  • Ciriani, Valentina
  • Cortadella, Jordi|||0000-0001-8114-250X
  • Costa, Marco
  • Villa, Tiziano
Bi-decomposition rewrites logic functions as the composition of simpler components. It is related to Boolean division, where a given function is rewritten as the product of a divisor and a quotient, but bi-decomposition can be defined for any Boolean operation of two operands. The key questions are how to find a good divisor and then how to compute the quotient. In this article, we select the divisor by approximation of the original function and then characterize by an incompletely specified function the full flexibility of the quotient for each binary operator. We target area-driven exact bi-decomposition, and we apply it to the bi-decomposition of Sum-of-Products (SOP) forms. We report experiments that exhibit significant gains in literals of SOP forms when rewritten as bi-decompositions with respect to the product operator. This suggests the application of this framework to other logic forms and binary operations, both for exact and approximate implementations., Anna Bernasconi and Valentina Ciriani are members of the Gruppo Nazionale Calcolo Scientifico-Istituto Nazionale di Alta Matematica (GNCS-INdAM), which provided partial support for this work. Valentina Ciriani was partially supported by project SERICS (PE00000014) under the NRRP MUR program funded by the EU - NGEU. Views and opinions expressed are however those of the authors only and do not necessarily reflect those of the European Union or the Italian MUR. Neither the European Union nor the Italian MUR can be held responsible for them. Jordi Cortadella was partially supported by funds from the Spanish Agencia Estatal de Investigación under grant PID2020-112581GB-C21 (MOTION), and from AGAUR under grant 2021-SGR-01419 (ALBCOM). Tiziano Villa was partially supported by MIUR, Project Italian Outstanding Departments, 2018-2022, by INdAM, GNCS 2023, Project Analisi simbolica e numerica di systemi ciberfisici and by INdAM, GNCS 2024, Project Certificazione, monitoraggio, ed interpretabilità in sistemi di intelligenza artificiale, Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Unification of drags and confluence of drag rewriting

  • Jouannaud, Jean Pierre
  • Orejas Valdés, Fernando|||0000-0002-3023-4006
Drags are a recent, natural generalization of terms which admit arbitrary cycles. A key aspect of drags is that they can be equipped with a composition operator so that rewriting amounts to replace a drag by another in a composition. In this paper, we develop a unification algorithm for drags that allows to check the local confluence property of a set of drag rewrite rules., This work is partially supported by MCIN/AEI /10.13039/501100011033 under grant PID2020-112581GB-C21., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

AntNetAlign: Ant colony optimization for network alignment

  • Rodríguez Corominas, Guillem
  • Blesa Aguilera, Maria Josep|||0000-0001-8246-9926
  • Blum, Christian
The code (and data) in this article has been certified as Reproducible by Code Ocean: (https://codeocean.com/). More information on the Reproducibility Badge Initiative is available at https://www.elsevier.com/physical-sciences-andengineering/computer-science/journals, Network Alignment (NA) is a hard optimization problem with important applications such as, for example, the identification of orthologous relationships between different proteins and of phylogenetic relationships between species. Given two (or more) networks, the goal is to find an alignment between them, that is, a mapping between their respective nodes such that the topological and functional structure is well preserved. Although the problem has received great interest in recent years, there is still a need to unify the different trends that have emerged from diverse research areas. In this paper, we introduce AntNetAlign, an Ant Colony Optimization (ACO) approach for solving the problem. The proposed approach makes use of similarity information extracted from the input networks to guide the construction process. Combined with an improvement measure that depends on the current construction state, it is able to optimize any of the three main topological quality measures. We provide an extensive experimental evaluation using real-world instances that range from Protein–Protein Interaction (PPI) networks to Social Networks. Results show that our method outperforms other state-of-the-art approaches in two out of three of the tested scores within a reasonable amount of time, specially in the important score. Moreover, it is able to obtain near-optimal results when aligning networks with themselves. Furthermore, in larger instances, our algorithm was still able to compete with the best performing method in this regard., Christian Blum and Guillem Rodríguez Corominas, Spain were supported by grants PID2019-104156GB-I00 and TED2021- 129319B-I00 funded by MCIN/AEI/10.13039/501100011033. Maria J. Blesa acknowledges support from AEI, Spain under grant PID2020-112581GB-C21 (MOTION) and the Catalan Agency for Management of University and Research Grants (AGAUR), Spain under grant 2017-SGR-786 (ALBCOM)., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Dynamic random graphs with vertex removal

  • Díaz Cort, Josep|||0000-0003-4422-0067
  • Lichev, Lyuben
  • Lodewijks, Bas
We introduce and analyse a Dynamic Random Graph with Vertex Removal (DRGVR) defined as follows. At every step, with probability p > 1/2, a new vertex is introduced and, with probability 1 - p, a vertex chosen uniformly at random among the present ones (if any) is removed from the graph together with all edges adjacent to it. In the former case, the new vertex connects by an edge to each existing vertex with probability inversely proportional to the number of vertices already present. We prove that the DRGVR converges to a local limit and determine this limit. Moreover, we analyse its component structure and distinguish a subcritical and a supercritical regime with respect to the existence of a giant component. As a byproduct of this analysis, we obtain upper and lower bounds for the critical parameter. Furthermore, we provide precise expression of the maximum degree (as well as inand out-degree for a natural orientation of the DRGVR). Several concentration and stability results complete the study., Funding Statement: Josep Díaz has been supported by grant MOTION, PID2020-112581GB-C21 from MCIN/ AEI /10.13039/501100011033. Bas Lodewijks has been supported by grant GrHyDy ANR-20-CE40-0002. Acknowledgments: We are thankful to Dieter Mitsche for useful discussions and suggestions, and to the two anonymous referees for multiple suggestions, corrections and improvements., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Continuous query engine to detect anomalous ATM transactions

  • Martín Canfrán, Fernando
  • Benedí García, Daniel
  • Duch Brown, Amalia|||0000-0003-4371-1286
  • Pasarella Sánchez, Ana Edelmira|||0000-0001-8315-4977
Nowadays data are in motion, change continuously and are –possibly– unbounded implying data sources that are also constantly evolving. From the data persistence point of view this reality breaks the usual paradigm of having dynamic but stable data sources. This, together with the increasing number applications based on data streams for taking critical decisions in real time, raises the need for re-thinking both the data and the query models to fit these new requirements. Therefore, under these circumstances, it seems reasonable that a suitable data model is a continuously evolving data graph. In this work we tackled the problem of querying continuously evolving data graphs in the context of ATM transactions, in particular anomalous ones. Under this context, evaluating continuous queries corresponds to recognize patterns usually associated with anomalous behaviors in the volatile subgraph of ATM transactions. We propose an evaluation process based on the dynamic pipeline computational model, a stream processing technique allowing the emission of alerts as soon as anomalous patterns are identified. Stream based Bank applications that monitor ATM transactions are direct beneficiaries of our proposal since they can continuously query data graphs to get “fresh” data as are produced, avoiding the computational overhead of having to discard non-valid data., This work has been supported by MCIN/AEI/10.13039/501100011033 under grant PID2020-112581GB-C21., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Social disruption games in signed networks

  • Molinero Albareda, Xavier|||0000-0002-5203-4347
  • Riquelme Csori, Fabian Rolando|||0000-0003-4491-0148
  • Serna Iglesias, María José|||0000-0001-9729-8648
Signed networks describe many real-world relations among users. Positive connections between two users or vertices generally mean good feelings between them, but negative connections mean bad feelings. A disruptor cycle in a graph is a cycle containing only one negative edge. A signed graph is known to be clusterable if and only if it does not contain a disruptor cycle. In this paper, we study the clusterability of a signed graph from the point of view of game theory introducing social disruption games on signed graphs. In these games, a coalition wins if the subgraph induced by the coalition is non-clusterable, i.e., it contains a disruptor cycle. Moreover, we study parameters and properties of players and compare them to other subclasses of simple games. In addition, we give some complexity results. In particular, we show that, unlike other subclasses of simple games, given a social disruption game, computing its length, deciding whether it is proper, or deciding whether it has a dummy player can be done in polynomial time. However, other problems, such as deciding whether the game is strong, or computing known power indices, remain computationally hard., "X. Molinero was partially supported by the Spanish Ministry of Economy and Competitiveness (MINECO) and the European Union (FEDER funds) [PID2019-104987GB-I00, JUVOCO] and the Catalan government [2021 SGR 01419 ALBCOM]. F. Riquelme was supported by the Fondecyt de Iniciación 11200113 from ANID, Chile. M. Serna was partially supported by the Spanish Agencia Estatal de Investigación [PID-2020-112581GB-C21, MOTION] and the Catalan government [2021 SGR 01419 ALBCOM].", Peer Reviewed, Objectius de Desenvolupament Sostenible::17 - Aliança per a Aconseguir els Objetius, Objectius de Desenvolupament Sostenible::11 - Ciutats i Comunitats Sostenibles
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Unbiased similarity estimators using samples

  • Martínez Parra, Conrado|||0000-0003-1302-9067
  • Viola Deambrosis, Alfredo
  • Wang, Jun
Computing a similarity measure (or a distance) between two complex objects is a fundamental building block for a huge number of applications in a wide variety of domains. Since many tasks involve computing such similarities among many pairs of objects, many algorithmic techniques and data structures have been devised in the past to reduce the number of similarity computations and to reduce the complexity of computing the similarity (e.g., dimension-reduction techniques). In this paper, we focus on computing the similarity of two sets and show that computing the similarity of two random samples drawn from the respective sets leads to an (asymptotically) unbiased estimator of the true similarity, with relative standard error going to zero as the size of the involved sets grows, and of course at a much lower computational cost as we compute the similarity of the significantly smaller samples. While this result has been known for a long time since Broder’s seminal paper (Broder, 1997) for the Jaccard similarity index, we show here that the result also holds for many other similarity measures, such as the well-known cosine similarity, Sørensen-Dice, the first and second Kulczynski coefficients, etc., This work has been supported by funds from the MOTION Project (Project PID2020-112581GB-C21) of the Spanish Ministry of Science & Innovation MCIN/AEI/10.13039/501100011033., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Accelerating the k-Means++ algorithm by using geometric information

  • Rodríguez i Corominas, Guillem
  • Blesa Aguilera, Maria Josep|||0000-0001-8246-9926
  • Blum, Christian
Clustering is a fundamental task in data analysis with applications across a wide range of fields, such as computer vision, pattern recognition, and data mining. Real-world use cases include social network analysis, medical imaging, market segmentation, and anomaly detection, to name a few. In this paper, we propose an acceleration of the exact k-means++ algorithm using geometric information, specifically the Triangle Inequality and additional norm filters, along with a two-step sampling procedure. Our experiments demonstrate that the accelerated version outperforms the standard k-means++ version in terms of the number of visited points and distance calculations, achieving greater speedup as the number of clusters increases. The version utilizing the Triangle Inequality is particularly effective for low-dimensional data, while the additional norm-based filter enhances performance in high-dimensional instances with greater norm variance among points. Additional experiments show the behavior of our algorithms when executed concurrently across multiple jobs and examine how memory performance impacts practical speedup., This work was supported in part by the Department of Research and Universities of the Government of Catalonia by means of an European Social Fund (ESF)-Founded Pre-Doctoral Grant of the Catalan Agency for Management of University and Research Grants (AGAUR) under Grant 2022 FI_B 00903, in part by the Agencia Estatal de Investigación (AEI) under Grant PID-2020-112581GB-C21 (MOTION), in part by Ministerio de Ciencia e Innovación (MCIN)/AEI/10.13039/501100011033 under Grant TED2021-129319B-I00 and Grant PID2022-136787NB-I00, and in part by the European Commission–NextGenerationEU, through Momentum CSIC Programme: Develop Your Digital Talent, under Project MMT24-IIIA-02., Peer Reviewed
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Small language models for less-resourced languages in a real-world scenario: The case for Catalan

  • Saurí Colomer, Roser
  • Sànchez-Ferreres, Josep
  • Padró, Lluís
  • Carmona Vargas, Josep
Small Language Models (SLMs), typically ranging from a few million to 10–15 billion parameters, offer a promising solution towards constraints imposed by platform size–particularly mobile and IoT devices–and by the requirements of many organizations such as SMEs, which need solutions that ensure data privacy while remaining cost-effective. Their compactness and efficiency provide digital sovereignty and flexibility, though with more limited general-purpose capabilities. This makes them especially sensitive when working with underrepresented languages, such as Catalan, due to interference from majority languages that can increase bias risk. This paper evaluates state-of-the-art SLMs in a real-world Catalan use case: an AI assistant for older adults, assessing both user interactions and structured function call generation. Our work, which contributes to the FREC initiative for deploying a connected SLM-based infrastructure under the Model Context Protocol, demonstrates that some SLMs are able to deliver high-quality performance even in resource-constrained, linguistically minority environments., This piece of work has been supported by MCIN/AEI/10.13039/501100011033 under grant PID2020-112581GB-C21 (MOTION). Also, by the European Union – NextGenerationEU, Spain’s Recovery, Transformation and Resilience Plan (RRP), in collaboration with the Catalan government (Generalitat de Catalunya), under grant SDC007/25/000055., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Typeface recognition and legibility metrics

  • Molinero Albareda, Xavier
  • Tàpias Anton, Montserrat
  • Balius Planelles, Andreu
  • Salvadó Arqués, Francisco María
In the digital age, people prefer digital content, but screen-related health concerns like eye strain and blue light emerge. Legibility gains importance in digital text, especially in fields like optometry and for those with low vision. Therefore, having good letter recognition ensures better readability of words and written language in general. This work focuses on defining three typeface legibility indices from the judgements of a group of 31 observers. Those indices are based on statistics, confusion matrices, and power indices from game theory. As far as we know, this is the first time that typeface legibility indices have been defined using game theory. These indices help us to globally assess how legible is a typeface. We apply them to three commonly used typefaces (Roboto, Helvetica and Georgia), and to a new one developed for the authors (Optotipica 5 v2022). This comparison helps us understand which typefaces are more legible according to the defined indices on digital screens. The major conclusions are: (1) The three indices are highly consistent pairwise; (2) Helvetica is the most legible typeface for uppercase letters, whilst Optotipica is the most legible for lowercase; (3) the two cases of Helvetica exhibit uniform high legibility metrics, ensuring optimal recognition regardless of letter case., X. Molinero was partially supported by the Spanish Ministry of Economy and Competitiveness (MINECO) and the European Union (FEDER funds) [PID2019-104987GB-I00, JUVOCO], the Spanish Agencia Estatal de Investigación [PID-2020-112581GB-C21, MOTION] and the Catalan government [2021 SGR 01419 ALBCOM], Peer Reviewed, Objectius de Desenvolupament Sostenible::1 - Fi de la Pobresa, Objectius de Desenvolupament Sostenible::3 - Salut i Benestar, Objectius de Desenvolupament Sostenible::10 - Reducció de les Desigualtats, Objectius de Desenvolupament Sostenible::11 - Ciutats i Comunitats Sostenibles, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

AntNetAlign: A software package for network alignment

  • Rodríguez i Corominas, Guillem
  • Blesa Aguilera, Maria Josep
  • Blum, Christian
In this paper we introduce AntNetAlign, an open-source tool (written in C++) that implements an Ant Colony Optimization (ACO) for solving the Network Alignment (NA) problem, a well-known hard optimization problem with important applications in different areas, such as biology or social networks. Specifically, given two input networks, the tool finds an alignment between them (i.e., a mapping between the respective nodes) that optimizes one out of the three main topological measures. Additionally, it can make use of user-defined pairwise similarities between nodes during its construction phase, allowing for the use of more application-dependent information in order to increase its performance. Results show that AntNetAlign outperforms other state-of-the-art algorithms in two out of the three aforementioned topological scores within a reasonable amount of time, and is able to achieve competitive results in the context of larger instances (Rodríguez Corominas et al., 2023). Furthermore, a new version of the algorithm, which makes use of Negative Learning, was able to further improve these results, specially in the EC score (Corominas et al., 2022)., Guillem Rodríguez Corominas gets support from the Department of Research and Universities of the Government of Catalonia by means of an ESF-founded pre-doctoral grant of the Catalan Agency for Management of University and Research Grants (AGAUR, Catalonia, Spain), under ref. number 2022 FI_B 00903. Christian Blum was supported by two grants funded by MCIN/AEI/10.13039/501100011033: AEI, Spain PID2019-104156GB-I00, and TED2021-129319B-I00. Maria J. Blesa acknowledges support from AEI, Spain under grant PID-2020-112581GB-C21 (MOTION) and the Catalan Agency for Management of University and Research Grants (AGAUR , Catalonia, Spain), under grant 2021-SGR-01419 (ALBCOM)., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Unification of drags and confluence of drag rewriting

  • Jouannaud, Jean Pierre
  • Orejas Valdés, Fernando
Drags are a recent, natural generalization of terms which admit arbitrary cycles. A key aspect of drags is that they can be equipped with a composition operator so that rewriting amounts to replace a drag by another in a composition. In this paper, we develop a unification algorithm for drags that allows to check the local confluence property of a set of drag rewrite rules., This work is partially supported by MCIN/AEI /10.13039/501100011033 under grant PID2020-112581GB-C21., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

On minimum vertex bisection of random d-regular graphs

  • Díaz Cort, Josep
  • Yasar Diner, Oznur
  • Serna Iglesias, María José
  • Serra Albó, Oriol
Minimum vertex bisection is a graph partitioning problem in which the aim is to find a partition of the vertices into two equal parts that minimizes the number of vertices in one partition set that have a neighbor in the other set. In this work we are interested in providing asymptotically almost surely upper bounds on the minimum vertex bisection of random d-regular graphs, for constant values of d. Our approach is based on analyzing a greedy algorithm by using the differential equation method. In this way, we obtain the first known non-trivial upper bounds for the vertex bisection number in random regular graphs. The numerical approximations of these theoretical bounds are compared with the emprical ones, and with the lower bounds from Kolesnik and Wormald (2014) [30]., J. Díaz and M. Serna were partially supported by the Spanish Agencia Estatal de Investigación under project MOTION, PID2020-112581 GB-C21. O.Y. Diner was partially supported by the Scientific and Technological Research Council Tübitak under project BIDEB 2219-1059B191802095 and by Kadir Has University under project 2018-BAP-08. O. Serra research was supported by the Spanish Agencia Estatal de Investigación under project CONTREWA, PID2020-113082 GB-I00., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación

Conformance checking: foundations, milestones and challenges

  • Carmona Vargas, Josep
  • Dongen, Boudewijn F. van
  • Weidlich, Matthias
By relating observed and modelled behaviour, conformance checking unleashes the full power of process mining. Techniques from this discipline enable the analysis of the quality of a process model discovered from event data, the identification of potential deviations, and the projection of real traces onto process models. This way, the insights gained from the available event data can be transferred to a richer conceptual level, amenable for a human interpretation. The aforementioned functionalities are grounded on the use of conformance checking artefacts that explicit the relation between observed and modelled behaviour. This chapter describes these artefacts, and builds upon them to gain evidence-based insights on the processes of an organization. Moreover, we overview the applications of conformance checking and propose a general framework that incorporates these applications. Finally, milestones and challenges of the field are outlined., This work has been supported by MCIN/AEI funds under grant PID2020-112581GB-C21., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Forward and backward linear threshold ranks

  • Blesa Aguilera, Maria Josep
  • García Rodríguez, Pau
  • Serna Iglesias, María José
We propose the FwLTR and BwLTR, two new centrality measures based on the Linear Threshold model. In contrast to the Linear Threshold rank (LTR), these measures differentiate between the incoming and the outgoing neighborhoods of the activation set that initiates the spreading process. Their rankings are distinguishable from the rest of the centrality measures considered traditionally. However, LTR and BwLTR behave quite similarly, while FwLTR is clearly different., Supported by AEI under grant PID-2020-112581GB-C21 (MOTION) and AGAUR under grant 2017-SGR-786 (ALBCOM)., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Partial match queries in quad-K-d trees

  • Duch Brown, Amalia
  • Martínez Parra, Conrado
Quad-K-d trees [Bereckzy et al., 2014] are a generalization of several well-known hierarchical Kdimensional data structures. They were introduced to provide a unified framework for the analysis of associative queries and to investigate the trade-offs between the cost of different operations and the memory needs (each node of a quad-K-d tree has arity 2 m for some m, 1 ≤ m ≤ K). Indeed, we consider here partial match – one of the fundamental associative queries – for several families of quad-K-d trees including, among others, relaxed K-d trees and quadtrees. In particular, we prove that the expected cost of a random partial match Pˆn that has s out of K specified coordinates in a random quad-K-d tree of size n is Pˆn ∼ β · n α where α and β are constants given in terms of K and s as well as additional parameters that characterize the specific family of quad-K-d trees under consideration. Additionally, we derive a precise asymptotic estimate for the main order term of Pn,q – the expected cost of a fixed partial match in a random quad-K-d tree of size n. The techniques and procedures used to derive the mentioned costs extend those already successfully applied to derive analogous results in quadtrees and relaxed K-d trees; our results show that the previous results are just particular cases, and states the validity of the conjecture made in [Duch et al., 2016] to a wider variety of multidimensional data structures., This work has been supported by funds from the MOTION Project (Project PID2020-112581GB-C21) of the Spanish Ministery of Science and Innovation MCIN/AEI/10.13039/501100011033., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Multidimension: a dimensionality extension of simple games

  • Molinero Albareda, Xavier
  • Riquelme Csori, Fabian Rolando
  • Roura Ferret, Salvador
  • Serna Iglesias, María José
In voting theory and social choice theory, decision systems can be represented as simple games, i.e., cooperative games defined through their players or voters and their set of winning coalitions. The weighted voting games form a well-known strict subclass of simple games, where each player has a voting weight so that a coalition wins if the sum of weights of their members exceeds a given quota. Since the number of winning coalitions can be exponential in the number of players, simple games can be represented much more compactly as intersections or unions of weighted voting games. A simple game’s dimension (codimension) is the minimum number of weighted voting games such that their intersection (union) is the given game. It is known there are voting systems with a high (co)dimension. This work introduces the multidimension as the minimum size of an expression with intersections and unions on weighted voting games necessary to obtain the considered simple game. We generalize this notion to subclasses of weighted voting games and analyze the generative properties of these subclasses. We also characterize the simple games with finite generalized multidimension over the set of weighted voting games without dummy players. We provide a comprehensive classification for simple games up to a certain number of players. These results complement similar classification results for generalized (co)dimensions. Our results show how generalized multidimension allows representing more simple games and more compactly, even for a small number of players and for subclasses., "Xavier Molinero was partially supported by the Spanish Ministry of Economy and Competitiveness (MINECO) and the European Union (FEDER funds) [PID2019-104987GB-I00, JUVOCO]. Fabián Riquelme was supported by the Fondecyt de Iniciación 11200113 from ANID, Chile. Maria Serna was partially supported by the Spanish Agencia Estatal de Investigación [PID-2020-112581GB-C21, MOTION]. Xavier Molinero, Salvador Roura, and Maria Serna were also partially supported by the Catalan government [2021 SGR 01419 ALBCOM]", Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Extremal coalitions for influence games through swarm intelligence-based methods

  • Riquelme Csori, Fabian Rolando
  • Olivares Ordenes, Rodrigo
  • Muñoz Peña, Francisco
  • Molinero Albareda, Xavier
  • Serna Iglesias, María José
An influence game is a simple game represented over an influence graph (i.e., a labeled, weighted graph) on which the influence spread phenomenon is exerted. Influence games allow applying different properties and parameters coming from cooperative game theory to the contexts of social network analysis, decision-systems, voting systems, and collective behavior. The exact calculation of several of these properties and parameters is computationally hard, even for a small number of players. Two examples of these parameters are the length and the width of a game. The length of a game is the size of its smaller winning coalition, while the width of a game is the size of its larger losing coalition. Both parameters are relevant to know the levels of difficulty in reaching agreements in collective decision-making systems. Despite the above, new bio-inspired metaheuristic algorithms have recently been developed to solve the NP-hard influence maximization problem in an efficient and approximate way, being able to find small winning coalitions that maximize the influence spread within an influence graph. In this article, we apply some variations of this solution to find extreme winning and losing coalitions, and thus efficient approximate solutions for the length and the width of influence games. As a case study, we consider two real social networks, one formed by the 58 members of the European Union Council under nice voting rules, and the other formed by the 705 members of the European Parliament, connected by political affinity. Results are promising and show that it is feasible to generate approximate solutions for the length and width parameters of influence games, in reduced solving time, "Funding Statement: F. Riquelme has been partially supported by Fondecyt de Iniciación 11200113, Chile, and by the SEGIB scholarship of Fundación Carolina, Spain; X. Molinero under grants PID2019-104987GB-I00 (JUVOCO); M. Serna under grants PID2020-112581GB-C21 (MOTION) and 2017-SGR-786 (ALBCOM)", Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

The analysis of partial match queries in random multidimensional trees: A selected survey

  • Duch Brown, Amalia
  • Hwang, Hsien-Kuei
  • Martínez Parra, Conrado
  • Neininger, Ralph
We analyze the probabilistic performance of partial match queries in random multidimensional search trees, using k-d trees (and their variants) and quadtrees, as primary examples. A partial match query aims to retrieve all points from a tree that match a given query point on a predetermined subset of coordinates. As one of the most basic associative searches, its analysis is foundational for evaluating more complex queries. This selection of data structures allows us to demonstrate common analytical techniques and offer a historical perspective on the field., The work of Amalia Duch and Conrado Martínez has been supported by funds from the MOTION Project (Project PID2020-112581GB-C21) of the Spanish Ministry of Science and Innovation MCIN/AEI/10.13039/501100011033., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

A computational framework based on the dynamic pipeline approach

  • Pasarella Sánchez, Ana Edelmira
  • Vidal Serodio, Maria Esther
  • Zoltán, Cristina
  • Royo Sales, Juan Pablo
© 2024 The Authors. Published by Elsevier Inc, Stream processing has inspired new computational approaches to facilitate effectiveness and efficiency. One such approach is the dynamic pipeline, which serves as a powerful computational model for stream processing. It is particularly well suited for solving problems that require incremental generation of results, making it an approach for scenarios where real-time analysis and responsiveness are critical. This paper aims to address a family of problems using the Dynamic Pipeline approach, and as a first step, we provide a comprehensive characterization of this problem family. In addition, we present the definition of a Dynamic Pipeline framework. To demonstrate the practicality of this framework, we present a proof of concept through its implementation and perform an empirical performance study. To this end, we focus on solving the problem of enumerating or listing the weakly connected components of a graph within the proposed framework. We provide two implementations of this algorithm to demonstrate the computational power and continuous behavior of the Dynamic Pipeline framework. The first implementation serves as a baseline for our experiments, representing an ad hoc solution based on the Dynamic Pipeline approach. In contrast, the second implementation is built on top of the developed framework. The observed results strongly support the suitability and effectiveness of the Dynamic Pipeline framework for implementing graph stream processing problems, especially those where continuous and real-time result generation is essential., This work has been partially supported by MCIN/ AEI /10.13039/501100011033 under grant PID2020-112581GB-C21 and by the Leibniz Association Germany, “Leibniz Best Minds: Programme for Women Professors”, project TrustKG-Transforming Data in Trustable Insights; Grant P99/2020., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Area-driven Boolean bi-decomposition by function approximation

  • Bernasconi, Anna
  • Ciriani, Valentina
  • Cortadella, Jordi
  • Costa, Marco
  • Villa, Tiziano
Bi-decomposition rewrites logic functions as the composition of simpler components. It is related to Boolean division, where a given function is rewritten as the product of a divisor and a quotient, but bi-decomposition can be defined for any Boolean operation of two operands. The key questions are how to find a good divisor and then how to compute the quotient. In this article, we select the divisor by approximation of the original function and then characterize by an incompletely specified function the full flexibility of the quotient for each binary operator. We target area-driven exact bi-decomposition, and we apply it to the bi-decomposition of Sum-of-Products (SOP) forms. We report experiments that exhibit significant gains in literals of SOP forms when rewritten as bi-decompositions with respect to the product operator. This suggests the application of this framework to other logic forms and binary operations, both for exact and approximate implementations., Anna Bernasconi and Valentina Ciriani are members of the Gruppo Nazionale Calcolo Scientifico-Istituto Nazionale di Alta Matematica (GNCS-INdAM), which provided partial support for this work. Valentina Ciriani was partially supported by project SERICS (PE00000014) under the NRRP MUR program funded by the EU - NGEU. Views and opinions expressed are however those of the authors only and do not necessarily reflect those of the European Union or the Italian MUR. Neither the European Union nor the Italian MUR can be held responsible for them. Jordi Cortadella was partially supported by funds from the Spanish Agencia Estatal de Investigación under grant PID2020-112581GB-C21 (MOTION), and from AGAUR under grant 2021-SGR-01419 (ALBCOM). Tiziano Villa was partially supported by MIUR, Project Italian Outstanding Departments, 2018-2022, by INdAM, GNCS 2023, Project Analisi simbolica e numerica di systemi ciberfisici and by INdAM, GNCS 2024, Project Certificazione, monitoraggio, ed interpretabilità in sistemi di intelligenza artificiale, Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

A stream processing-based algorithm for maintaining minimum spanning forests of evolving graphs

  • Benedí García, Daniel
  • Duch Brown, Amalia
  • Pasarella Sánchez, Ana Edelmira
In this work we introduce a concurrent/parallel adaptation of Kruskal algorithm based on the dynamic pipeline approach. This is, the input (undirected) graph is given by a stream of weighted edges and it is dynamically created and maintained in a distributed way along a pipeline of stateful stages. To be concrete, firstly an initial graph is created and then, whenever the graph evolves because of edges are added, removed or updated, the minimum spanning tree (forest) according to the current graph can be computed and output immediately. Moreover, we provide a working implementation in the Go programming language. Go is suitable to dynamic pipelines’ implementations thanks to its communication channels and co-routines. We show experimentally that our algorithm scales well to a large number of processes and that it is competitive against the classic sequential Kruskal algorithm and a well known parallelized version of the Kruskal algorithm. Our experimental study is done for a large class of dynamic random graphs –including several densities and sizes– and some real dynamic graphs., This work has been funded by MCIN/AEI/10.13039/501100011033 under grant PID2020-112581GB-C21., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

How can graph databases and reasoning be combined and integrated?

  • Pasarella Sánchez, Ana Edelmira
Nowadays the graph data model has been accepted as one of the most suitable data models to formalize relationships among entities of many domains. Deductive databases based on the Datalog language have been used to deduce new information from large amounts of data. Most of the attempts to combine logic and graph databases are based on translating knowledge in graph databases into Datalog and then use its inference engine. We aim to open the discussion about combining graph databases and a graph-oriented logic to define «native» deductive graph databases. This is, graph databases equipped with an inference mechanism based on graph based logic. To be concrete, we plan to use the recently introduced graph navigational logic., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Unbiased similarity estimators using samples

  • Martínez Parra, Conrado
  • Viola Deambrosis, Alfredo
  • Wang,Jun
Computing a similarity measure (or a distance) between two complex objects is a fundamental building block for a huge number of applications in a wide variety of domains. Since many tasks involve computing such similarities among many pairs of objects, many algorithmic techniques and data structures have been devised in the past to reduce the number of similarity computations and to reduce the complexity of computing the similarity (e.g., dimension-reduction techniques). In this paper, we focus on computing the similarity of two sets and show that computing the similarity of two random samples drawn from the respective sets leads to an (asymptotically) unbiased estimator of the true similarity, with relative standard error going to zero as the size of the involved sets grows, and of course at a much lower computational cost as we compute the similarity of the significantly smaller samples. While this result has been known for a long time since Broder’s seminal paper (Broder, 1997) for the Jaccard similarity index, we show here that the result also holds for many other similarity measures, such as the well-known cosine similarity, Sørensen-Dice, the first and second Kulczynski coefficients, etc., This work has been supported by funds from the MOTION Project (Project PID2020-112581GB-C21) of the Spanish Ministry of Science & Innovation MCIN/AEI/10.13039/501100011033., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Theoretical and empirical analysis of cost-function merging for implicit hitting set WCSP solving

  • Larrosa Bondia, Francisco Javier
  • Martínez Parra, Conrado
  • Rollón Rico, Emma
The Implicit Hitting Set (HS) approach has shown very effective for MaxSAT solving. However, only preliminary promising results have been obtained for the very similar Weighted CSP framework. In this paper we contribute towards both a better theoretical understanding of the HS approach and a more effective HS-based solvers for WCSP. First, we bound the minimum number of iterations of HS thanks to what we call distinguished cores. Then, we show a source of inefficiency by introducing two simple problems where HS is unfeasible. Next, we propose two reformulation methods that merge cost-functions to overcome the problem. We provide a theoretical analysis that quantifies the magnitude of the improvement of each method with respect to the number of iterations of the algorithm. In particular, we show that the reformulations can bring an exponential number of iterations down to a constant number in our working examples. Finally, we complement our theoretical analysis with two sets of experiments. First, we show that our results are aligned with real executions. Second, and most importantly, we conduct experiments on typical benchmark problems and show that cost-function merging may be heuristically applied and it may accelerate HS algorithms by several orders of magnitude. In some cases, it even outperforms state-of-the-art solvers., The work of Javier Larrosa and Emma Rollon was supported by grant PID2021-122830OB-C43, funded by MCIN/AEI/ 10.13039/501100011033 and by “ERDF: A way of making Europe”. The work of Conrado Martínez was supported by grant PID2020-112581GB-C21 (MOTION Project), funded by MCIN/AEI/10.13039/501100011033., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Coinductive techniques for checking satisfiability of generalized nested conditions

  • Stoltenow, Lara
  • König, Barbara
  • Schneider, Sven
  • Corradini, Andrea
  • Lambers, Leen
  • Orejas Valdés, Fernando
We study nested conditions, a generalization of first-order logic to a categorical setting, and provide a tableau-based (semi-decision) procedure for checking (un)satisfiability and finite model generation. This generalizes earlier results on graph conditions. Furthermore we introduce a notion of witnesses, allowing the detection of infinite models in some cases. To ensure completeness, paths in a tableau must be fair, where fairness requires that all parts of a condition are processed eventually. Since the correctness arguments are non-trivial, we rely on coinductive proof methods and up-to techniques that structure the arguments. We distinguish between two types of categories: categories where all sections are isomorphisms, allowing for a simpler tableau calculus that includes finite model generation; in categories where this requirement does not hold, model generation does not work, but we still obtain a sound and complete calculus., Andrea Corradini: Research partially supported by the Italian MUR under the PRIN 20228KXFN2 “STENDHAL” and by the University of Pisa under the PRA 2022_99 “FM4HD”. Fernando Orejas: Research partially supported by MCIN/ AEI /10.13039/501100011033 under grant PID2020-112581GB-C21., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Traversal games in K-shell decomposition

  • Molinero Albareda, Xavier
  • Riquelme Csori, Fabian Rolando
  • Serna Iglesias, María José
In network science, K-shell decomposition is a well-known method for efficiently identifying structural hierarchical shells or layers within a network. In this hierarchy, the innermost non-empty shell contains actors with the highest connectivity, while the peripheral shell includes actors with fewer connections or less integration into the network. Rather than considering the outer shells less relevant than the inner ones, this paper introduces K-shell traversal games, as a family of simple cooperative games, whose winning coalitions consist of actors connecting the outermost to the innermost layer of the hierarchical structure, facilitating the flow of information or resources to key representatives across different shells. We analyze several properties of these games, their coalitions, and actors (or players). We also study their efficient computation, as well as their potential real-world applications based on connectivity analysis across hierarchical network layers., This work has been partially supported by the Spanish Agencia Estatal de Investigación AEI/10.13039/501100011033 (Project PID2020112581GB-C21 MOTION). F. Riquelme was supported by the postdoctoral fellowship awarded by the Carolina Foundation (Spain) and the University of Valparaíso, Chile (2024–2025), to carry out a postdoctoral stay at the Polytechnic University of Catalonia., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Improved reconstruction of random geometric graphs

  • Dani, Varsha
  • Díaz Cort, Josep
  • Hayes, Thomas P.
  • Moore, Cristopher
Embedding graphs in a geographical or latent space, i.e. inferring locations for vertices in Euclidean space or on a smooth manifold or submanifold, is a common task in network analysis, statistical inference, and graph visualization. We consider the classic model of random geometric graphs where n points are scattered uniformly in a square of area n, and two points have an edge between them if and only if their Euclidean distance is less than r. The reconstruction problem then consists of T A inferring the vertex positions, up to the symmetries of the square, given only the adjacency matrix of the resulting graph. We give an algorithm that, if r = nα for α > 0, with high probability reconstructs the vertex positions with a maximum error of O(nβ) where β = 1/2 − (4/3)α, until α ≥3/8 where β =0 and the error becomes O(√ log n). This improves over earlier results, which E were unable to reconstruct with error less than r. Our method estimates Euclidean distances using a hybrid of graph distances and short-range estimates based on the number of common neighbors. We extend our results to the surface of the sphere in R3 and to hypercubes in any constant dimension., Josep Díaz: Partially supported by PID-2020-112581GB-C21 (MOTION). Thomas P. Hayes: Partially supported by NSF grant CCF-1150281. Cristopher Moore: Partially supported by NSF grant IIS-1838251., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

The semantics of GQL-like path queries

  • Orejas Valdés, Fernando
  • Pino Blanco, Elvira
The success of graph databases (GDBs) has caused the development of several dozens of GDB products by companies like Neo4j, Oracle, Amazon, IBM or SAP. In parallel, several graph query languages have been designed for querying these GDBs, like Cypher for Neo4j, PGQL for Oracle, or GSQL for TigerGraph, which actually are quite similar. This situation has led to propose the creation of a unifying standard for graph query languages. This standard is currently under development, and is called GQL. In a previous paper we defined a logical and an operational semantics for a core language similar to Cypher, showing that the operational semantics is sound and complete with respect to the logical one. However, GQL has gone beyond the expressive power of the above mentioned languages in several senses. Therefore, in the current work, our aim is to redefine the semantics that we gave for Cypher-like languages to a core subset of GQL., This work is partially supported by MCIN/ AEI /10.13039/501100011033 under grant PID2020-112581GB-C21., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

FastKPP: An exact accelerated k-means++ algorithm

  • Rodríguez i Corominas, Guillem
  • Blesa Aguilera, Maria Josep
  • Blum, Christian
In this paper, we present FastKpp, a C++ implementation of an exact accelerated 𝑘-means++ algorithm using two geometry-aware filters: one based on the Triangle Inequality (TIE) and another based on point norms. Both provably preserve the original 𝐷2 sampling distribution while avoiding redundant distance computations. The library provides a header-only API, a command-line tool, and a fully reproducible capsule. Experiments show substantial reductions in distance computations and speedups that increase with k (with typical median between 2 and 8). Furthermore, FastKpp outperforms other state-of-the-art exact acceleration techniques. Results are reproducible via the public GitHub repository and Code Ocean capsule., This work was supported in part by the Department of Research and Universities of the Government of Catalonia by means of an European Social Fund (ESF)-Founded Pre-Doctoral Grant of the Catalan Agency for Management of University and Research Grants (AGAUR) under Grant 2022 FI_B 00903, in part by the Agencia Estatal de Investigación (AEI) under grants PID-2020-112581GB-C21 (MOTION) and PID2022-136787NB-I00 (ACISUD), and in part by the European Commission–NextGenerationEU, through Momentum CSIC Programme: Develop Your Digital Talent, under Project MMT24-IIIA-02., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Weightedness measures from inequality systems

  • Albareda Sambola, Maria
  • Molinero Albareda, Xavier
  • Roura Ferret, Salvador
A simple game is a cooperative game where some coalitions among players or voters became the (monotonic) set of winning coalitions, and the other ones form the set of losing coalitions. It is well-known that weighted voting games form a strict subclass of simple games, where each player has a voting weight so that a coalition wins if and only if the sum of weights of their members exceeds a given quota, otherwise it loses. This work studies how far away a simple game is for being representable as a weighted voting game, which allows for a more compact representation. There are several measures that determine the weightedness of a simple game, such as the dimension, the trade-robustness, the critical threshold value associated with the a-roughly weightedness property, etc. In this work we propose some new weightedness measures, all based on linear programming. In general terms, for a given simple game, a linear program is used to identify its weightedness: (i) the ¿-roughly value (µe ), (ii) the Z+ -roughly value (µZ+ ), (iii) the ¿-roughly value (µ¿ ), and (iv) the outlier value (¿M ). We show a close relation between the known critical threshold value of weightedness and the new measure µ¿ . Finally, we also present an exhaustive comparison of weightedness measures for simple games with up to six players., M. Albareda-Sambola was funded by MCIN/AEI/10.13039/501100011033/FEDER-EU project PID2022-139219OB-I00 and RED2022-134149-T. X. Molinero was partially supported by MCIN/AEI/10.13039/501100011033 under grant PID2020-112581GB-C21 (MOTION). X. Molinero and S. Roura were also partially supported by the Catalan government [2021 SGR 01419 ALBCOM]., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

A proposal for an Educational Well-Being Index (EWI) for undergraduate course design

  • Blesa Aguilera, Maria Josep
  • Duch Brown, Amalia
  • Gabarró Vallès, Joaquim
  • Serna Iglesias, María José
Every day it is more common to hear around us about the publication of studies, surveys or statistical results about the well-being of people, workers, women in a given country. Indeed, as university professors, our work cannot be independent of the level of well-being of our students. So, in this work, we propose a methodology to asses the students well-being inside a course implementation by what we call the educational well-being index (EWI). We start with a survey that gathers those factors that computing courses’ students at our university –of two different levels and majors– consider most important. Our second step is the evaluation –by a group of teachers– of the presence of those factors in different educational models of implementation of the courses. We use principal component analysis to extract, from the student data, the valuations that they expressed in the survey: the principal component of their own measurements on well-being. We work only with the coefficients of the first dimension of the principal component. The third step is a (subjective) valuation of the topics addressed in the survey when considering a particular educational model. Finally, we gather everything together to obtain a well-being index of an educational model that allows their comparison. Besides the methodology, we present and analyze the values obtained from our case study., Supported by MCIN/AEI/10.13039/501100011033 under grant PID2020-112581GB-C21 (MOTION)., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

NTAC: Neuronal type assignment from connectivity

  • Schwartzman, Gregory
  • Jourdan, Ben
  • García Soriano, David
  • Matsliah, Arie
Recent advances in electron microscopy and computer vision now allow the reconstruction of complete wiring diagrams, or connectomes, of animal brains. This creates an urgent need for methods that can automatically identify neuronal cell types directly from these large connectivity datasets. Here we show that synaptic connectivity alone can be used to assign neurons to cell types with high accuracy. We introduce NTAC (Neuronal Type Assignment from Connectivity), which groups neurons based only on connectivity. NTAC has two forms: a semi-supervised one that leverages a small fraction of labeled neurons to infer the types of all others, and an unsupervised one that requires no labels at all. Applied to multiple state-of-the-art fruit fly brain connectomes, NTAC achieves high accuracy within only minutes on a laptop, demonstrating that connectivity provides a powerful and scalable basis for classifying neuronal cell types across the brain., AM was supported by funding provided through grants to Murthy and Seung from the NIH BRAIN Initiative (RF1 MH117815, RF1 MH129268, U24 NS126935). GS was supported by the following research grants: KAKENHI 25K00370, JST ASPIRE JPMJAP2302 and JST CRONOS JPMJCS24K2. BJ was supported through an EPSRC Early Career Fellowship (EP/T00729). DGS was supported by the Spanish Agencia Estatal de Investigación AEI/10.13039/ 501100011033 (Project PID2020-112581GB-C21 MOTION)., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Social disruption games in signed networks

  • Molinero Albareda, Xavier
  • Riquelme Csori, Fabian Rolando
  • Serna Iglesias, María José
Signed networks describe many real-world relations among users. Positive connections between two users or vertices generally mean good feelings between them, but negative connections mean bad feelings. A disruptor cycle in a graph is a cycle containing only one negative edge. A signed graph is known to be clusterable if and only if it does not contain a disruptor cycle. In this paper, we study the clusterability of a signed graph from the point of view of game theory introducing social disruption games on signed graphs. In these games, a coalition wins if the subgraph induced by the coalition is non-clusterable, i.e., it contains a disruptor cycle. Moreover, we study parameters and properties of players and compare them to other subclasses of simple games. In addition, we give some complexity results. In particular, we show that, unlike other subclasses of simple games, given a social disruption game, computing its length, deciding whether it is proper, or deciding whether it has a dummy player can be done in polynomial time. However, other problems, such as deciding whether the game is strong, or computing known power indices, remain computationally hard., "X. Molinero was partially supported by the Spanish Ministry of Economy and Competitiveness (MINECO) and the European Union (FEDER funds) [PID2019-104987GB-I00, JUVOCO] and the Catalan government [2021 SGR 01419 ALBCOM]. F. Riquelme was supported by the Fondecyt de Iniciación 11200113 from ANID, Chile. M. Serna was partially supported by the Spanish Agencia Estatal de Investigación [PID-2020-112581GB-C21, MOTION] and the Catalan government [2021 SGR 01419 ALBCOM].", Peer Reviewed, Objectius de Desenvolupament Sostenible::17 - Aliança per a Aconseguir els Objetius, Objectius de Desenvolupament Sostenible::11 - Ciutats i Comunitats Sostenibles, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Mathematical models to analyze Lua hybrid tables

  • Martínez Parra, Conrado
  • Nicaud, Cyril
  • Rotondo, Pablo
Lua (Ierusalimschy et al., 1996) is a well-known scripting language, popular among many programmers, most notably in the gaming industry. Remarkably, the only data-structuring mechanism in Lua is given by associative arrays, called tables. With Lua 5.0, the reference implementation of Lua introduced hybrid tables to implement tables using both a hashmap and a dynamically growing array combined together: the values associated with integer keys are stored in the array part, when suitable, everything else is stored in the hashmap. All this is transparent to the user, who gets a unique simple interface to handle tables. In this paper we carry out a theoretical analysis of the performance of Lua's tables, by considering various worst-case and probabilistic scenarios. In particular, we uncover some problematic situations for the simple probabilistic model where we add a new key with some fixed probability p > 1/2 and delete a key with probability 1-p: the cost of performing T such operations is proved to be O(TlogT) with high probability, where linear complexity would be assumed for such data structure. If there is no deletion, we prove that the tables behave better overall. In particular, we establish that inserting the T integers from 1 to T in a random order is done in an essentially linear time., The work of the first author has been supported by funds from project MOTION (Project PID2020-112581GB-C21) of the Spanish Ministry of Science & Innovation MCIN/AEI/10.13039/501100011033., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Nash’s bargaining problem and the scale-invariant Hirsch citation index

  • Freixas Bosch, Josep
  • Hoerl, Roger
  • Zwicker, William
A number of citation indices have been proposed for measuring and ranking the research publication records of scholars. Some of the best known indices, such as those proposed by Hirsch and Woeginger, are designed to reward most highly those records that strike some balance between productivity (number of papers published) and impact (frequency with which those papers are cited). A large number of rarely cited publications will not score well, nor will a very small number of heavily cited papers. We discuss three new citation indices, one of which was independently proposed in Fenner et al. (PLOS ONE 13(7): e0200098, 2018). Each rests on the notion of scale invariance, fundamental to John Nash’s solution of the two-person bargaining problem. Our main focus is on one of these—a scale-invariant version of the Hirsch index. We argue that it has advantages over the original; it produces fairer rankings within subdisciplines, is more decisive (discriminates more finely, yielding fewer ties) and more dynamic (growing over time via more frequent, smaller increments), and exhibits enhanced centrality and tail balancedness. Simulations suggest that scale invariance improves robustness under Poisson noise, with increased decisiveness having no cost in terms of the number of “accidental” reversals, wherein random irregularities cause researcher A to receive a lower index value than B, although A’s productivity and impact are both slightly higher than B’s. Moreover, we provide an axiomatic characterization of the scale-invariant Hirsch index, via axioms that bear a close relationship, in discrete analogue, to those used by Nash (Econometrica 18(2):155–162, 1950). This argues for the mathematical naturality of the new index., The first author’s research was partially supported by MCIN/AEI/10.13039/501100011033 under grant PID2020-112581GB-C21 (MOTION). The third author’s work was partially supported by the CY Initiative of Excellence (grant “Investissements d’Avenir” ANR-16-IDEX-0008) and was developed partly during the author’s stay at CY Advanced Studies. We thank Denis Bouyssou for his informative comments, and the two referees for many helpful suggestions, all of which improved the manuscript., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

The metric dimension of sparse random graphs

  • Díaz Cort, Josep
  • Hartle, Harrison
  • Moore, Cristopher
In 2013, Bollobás, Mitsche, and Pralat gave upper and lower bounds for the likely metric dimension of random Erdos-Rényi graphs G(n,p) for a large range of expected degrees. However, their results only apply when d=pn=omega(log^5 n), leaving open sparser random graphs with d=O(log^5 n) or d=o(log^5n). Here we provide upper and lower bounds on the likely metric dimension of G(n,p) in a range of d starting just above the connectivity transition, i.e., where d=c log n for some constant c>1, up to d=O(log^5 n). Our lower bound technique is based on an entropic argument which is weaker but more general than the use of Suen's inequality by Bollobás, Mitsche, and Pralat, whereas our upper bound is similar to theirs., This work was supported by the Spanish Ministry of Science and Innovation, projectPID2020-112581GB-C21 MOTION (J. Díaz), the Santa Fe Institute (H. Hartle, C. Moore),and the Robert Wood Johnson Foundation (C. Moore)., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Tight bounds for an accelerated k-means++ algorithm

  • Rodríguez i Corominas, Guillem
  • Blesa Aguilera, Maria Josep
  • Blum, Christian
In this paper, we improve a recently introduced accelerated k-means++ algorithm by proposing a dynamic method for calculating bounds during its execution. This approach produces high-quality bounds without requiring a full iteration over the dataset, using the Triangle Inequality and the norm of the points for efficient computation. We propose three evaluation metrics to assess the quality of the calculated bounds and analyze their behavior across a diverse dataset. Results show that this dynamic method outperforms the traditional approach of initializing bounds at the end of the process, before the execution of the k-means algorithm., The research presented in this paper was supported by grant 2022 FI_B 00903 funded by the AGAUR; grant PID-2020-112581GB-C21 (MOTION) funded by the AEI; grants TED2021-129319B-I00 and PID2022-136787NB-I00 funded by MCIN/AEI/10.13039/501100011033; and project MMT24-IIIA-02 funded by Red.es, Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación

A probabilistic model revealing shortcomings in Lua’s hybrid tables

  • Martínez Parra, Conrado
  • Nicaud, Cyril
  • Rotondo, Pablo
Lua (Ierusalimschy et al., 1996) is a well-known scripting language, popular among many programmers, most notably in the gaming industry. Remarkably, the only data-structuring mechanism in Lua, is an associative array called a table. With Lua 5.0, the reference implementation of Lua introduced hybrid tables to implement tables using both a hash table and a dynamically growing array combined together: the values associated with integer keys are stored in the array part, when suitable. All this is transparent to the user, which has a unique simple interface to handle tables. In this paper we carry out a theoretical analysis of the performance of Lua ’s tables, by considering various worst-case and probabilistic scenarios. In particular, we uncover some problematic situations for the simple probabilistic model where we add a new key with some fixed probability p>1/2 and delete a key with probability 1−p: the cost of performing T such operations is proved to be Ω(TlogT) with high probability, instead of linear in T., The work of the first author has been supported by funds from project MOTION (Project PID2020-112581GB-C21) of the Spanish Ministry of Science & Innovation MCIN/AEI/10.13039/501100011033., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Rainbow connectivity of multilayered random geometric graphs

  • Díaz Cort, Josep
  • Diner, Oznur Y.
  • Serra Albó, Oriol
  • Serna Iglesias, María José
An edge-colored multigraph G is rainbow connected if every pair of vertices is joined by at least one rainbow path, i.e., a path where no two edges are of the same color. In the context of multilayered networks, we introduce the notion of multilayered random geometric graphs, from h = 2 independent random geometric graphs G(n,r) on the unit square. We define an edge-coloring by coloring the edges according to the copy of G(n,r) they belong to and study the rainbow connectivity of the resulting edge-colored multigraph. We show that r(n) = lnn nh-1 1/2h , is a threshold of the radius for the property of being rainbow connected. This complements the known analogous results for the multilayered graphs defined on the Erdos–Rényi random model., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Negative learning ant colony optimization for network alignment

  • Rodríguez Corominas, Guillem
  • Blum, Christian
  • Blesa Aguilera, Maria Josep
The Network Alignment problem is a hard Combinatorial Optimization problem with a wide range of applications, especially in computational biology. Given two (or more) networks, the goal is to find a mapping between their respective nodes that preserves the topological and functional structure of the networks. In this work we extend a novel ant colony optimization approach for network alignment by adding a recently proposed Negative Learning mechanism. In particular, information for Negative Learning is obtained by solving sub-instances of the tackled problem instances at each iteration by means of an Integer Linear Programming solver. The results show that the proposed algorithm not only outperforms the standard ant colony optimization approach but also current state-of-the-art methods from the literature., M. Blesa acknowledges support by AGAUR (GENCAT) under grant 2017-SGR-786 (ALBCOM). Moreover, the authors acknowledge support by MCIN/AEI/10.13039/501100011033 under grant PID2020-112581GB-C21 (MOTION) and grant PID2019-104156GB-I00 (CISUSTAIN)., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Median and hybrid median K-dimensional trees

  • Duch Brown, Amalia
  • Martínez Parra, Conrado
  • Pons, Mercè
  • Roura Ferret, Salvador
We consider here two new variants of K-dimensional binary search trees (K-d trees): median K-d trees and hybrid-median K-d trees. These two kinds of trees are designed with the aim to get a tree as balanced as possible. This goal is attained by heuristics that choose for each node of the K-d tree the appropriate coordinate to discriminate. In the case of median K-d trees, the chosen dimension to discriminate at each node is the one whose point value at that node is the most centered one. In hybrid-median K-d trees, the heuristic is similar except that it should be followed in a cyclic way, meaning that, at every path of the tree, no dimension can be re-selected to discriminate unless all the other dimensions have already been selected. We study the expected internal path length (IPL) and the expected cost of random partial match (PM) searches in both variants of K-d trees. For both variants, we prove that the expected IPL is of the form cK⋅nlog2n+lower order terms , and the expected cost of PM is of the form Θ(nα) with α=α(s,K) . We give the explicit equations satisfied by the constants cK and the exponents α which we can then numerically solve. Moreover, we prove that as K→∞ the trees in both variants tend to be perfectly balanced (cK→1 ) and we also show that α→log2(2−s/K) for median K -d trees when K→∞ . In the case of hybrid median K -d trees we conjecture that α→1−s/K , when K→∞ , which would be optimal., This work has been supported by funds from the MOTION Project (Project PID2020-112581GB-C21) of the Spanish Ministery of Science & Innovation MCIN/AEI/10.13039/501100011033., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

The multicolored graph realization problem

  • Díaz Cort, Josep
  • Yasar Diner, Oznur
  • Serna Iglesias, María José
  • Serra Albó, Oriol
We introduce the multicolored graph realization problem (MGR). The input to this problem is a colored graph (G, φ), i.e., a graph G together with a coloring φ on its vertices. We associate each colored graph (G, φ) with a cluster graph (Gφ ) in which, after collapsing all vertices with the same color to a node, we remove multiple edges and self-loops. A set of vertices S is multicolored when S has exactly one vertex from each color class. The MGR problem is to decide whether there is a multicolored set S so that, after identifying each vertex in S with its color class, G[S] coincides with Gφ . The MGR problem is related to the well-known class of generalized network problems, most of which are NP-hard, like the generalized Minimum Spanning Tree problem. The MGR is a generalization of the multicolored clique problem, which is known to be W [1]-hard when parameterized by the number of colors. Thus, MGR remains W [1]-hard, when parameterized by the size of the cluster graph. These results imply that the MGR problem is W [1]-hard when parameterized by any graph parameter on Gφ , among which lies treewidth. Consequently, we look at the instances of the problem in which both the number of color classes and the treewidth of Gφ are unbounded. We consider three natural such graph classes: chordal graphs, convex bipartite graphs and 2-dimensional grid graphs. We show that MGR is NP-complete when Gφ is either chordal, biconvex bipartite, complete bipartite or a 2-dimensional grid. Our reductions show that the problem remains hard even when the maximum number of vertices in a color class is 3. In the case of the grid, the hardness holds even for graphs with bounded degree. We provide a complexity dichotomy with respect to cluster size ., J. Díaz and M. Serna are partially supported by funds from the Spanish Agencia Estatal de Investigación under grant PID2020-112581GB-C21 (MOTION), and from AGAUR under grant 2017-SGR-786 (ALBCOM). Ö. Y. Diner is partially supported by the Scientific and Technological Research Council Tübitak under project BIDEB 2219-1059B191802095 and by Kadir Has University under project 2018-BAP-08. O. Serra is supported by the Spanish Agencia Estatal de Investigación under grant PID2020-113082GB-I00., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

On the enumeration of resolute majority rules

  • Freixas Bosch, Josep
  • Samaniego Vidal, Daniel
This paper considers resolute decision rules in which each voter may vote “yes", “abstain" or vote “no", and the outcome is “yes" or “no". The model we consider is more general than that of simple games since the input admits abstention or indecision, but it is more specialized since it assumes the properties of monotonicity and anonymity. Many subclasses of these resolute decision rules have been studied in the literature from an axiomatic point of view. The purpose of this work is to enumerate these subclasses as a function of the number of voters., This research was partially supported by the Spanish Agencia Estatal de Investigación [PID-2020-112581GB-C21, MOTION] and the Agència de Gestió d’Ajuts Universitaris i de Recerca (AGAUR) of the Government of Catalonia under project 2017 SGR 786 (ALBCOM). We greatly appreciate the comments of two anonymous referees who have contributed to improve the presentation of this work., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

SoftBinReduce: data reduction for color quantization through soft binning

  • Rodríguez i Corominas, Guillem
  • Blesa Aguilera, Maria Josep
  • Blum, Christian
In this paper, we propose SoftBinReduce, a data reduction method for Color Quantization. Our approach consists of four main steps: (1) identifying representatives in each channel, (2) generating three-dimensional bins, (3) distributing pixel values using a soft binning technique, and (4) repositioning the resulting bins. Additionally, we introduce an adapted Sort-Means algorithm for the Pixel Mapping phase, providing a strong initial guess. We conduct an extensive experimental evaluation primarily using the CQ100 dataset, but also the older Kodak and USC-SIPI datasets. We compare our method to two well-known data reduction techniques from the literature: pseudo-random and quasi-random sampling. The results demonstrate that our method outperforms both in terms of NMSE error versus the achieved speedup, particularly when the data is significantly reduced and with a higher number of colors in the generated palette. Moreover, an ablation study shows that all components of our method are necessary for producing high-quality results., Open Access funding provided thanks to the CRUE-CSIC agreement with Springer Nature. Guillem Rodríguez Corominas acknowledges support from the Department of Research and Universities of the Government of Catalonia by means of an ESF-founded pre-doctoral grant of the Catalan Agency for Management of University and Research Grants (AGAUR), under ref. number 2022 FI_B 00903. Maria J. Blesa acknowledges support from AEI under MICINN grant PID-2020-112581GB-C21 (MOTION). Christian Blum was supported by two grants funded by MCIN/ AEI/10.13039/501100011033: TED2021-129319B-I00 and PID2022-136787NB-I00., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Affirmative sampling: theory and applications

  • Lumbroso, Jérémie
  • Martínez Parra, Conrado
Affirmative Sampling is a practical and efficient novel algorithm to obtain random samples of distinct elements from a data stream. Its most salient feature is that the size S of the sample will, on expectation, grow with the (unknown) number n of distinct elements in the data stream. As any distinct element has the same probability to be sampled, and the sample size is greater when the “diversity” (the number of distinct elements) is greater, the samples that Affirmative Sampling delivers are more representative than those produced by any scheme where the sample size is fixed a priori - hence its name. Our algorithm is straightforward to implement, and several implementations already exist., This work has been supported by funds from the MOTION Project (Project PID2020-112581GB-C21) of the Spanish Ministry of Science & Innovation MCIN/AEI/10.13039/501100011033, and by Princeton University, and its Department of Computer Science., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

AntNetAlign: Ant colony optimization for network alignment

  • Rodríguez Corominas, Guillem
  • Blesa Aguilera, Maria Josep
  • Blum, Christian
The code (and data) in this article has been certified as Reproducible by Code Ocean: (https://codeocean.com/). More information on the Reproducibility Badge Initiative is available at https://www.elsevier.com/physical-sciences-andengineering/computer-science/journals, Network Alignment (NA) is a hard optimization problem with important applications such as, for example, the identification of orthologous relationships between different proteins and of phylogenetic relationships between species. Given two (or more) networks, the goal is to find an alignment between them, that is, a mapping between their respective nodes such that the topological and functional structure is well preserved. Although the problem has received great interest in recent years, there is still a need to unify the different trends that have emerged from diverse research areas. In this paper, we introduce AntNetAlign, an Ant Colony Optimization (ACO) approach for solving the problem. The proposed approach makes use of similarity information extracted from the input networks to guide the construction process. Combined with an improvement measure that depends on the current construction state, it is able to optimize any of the three main topological quality measures. We provide an extensive experimental evaluation using real-world instances that range from Protein–Protein Interaction (PPI) networks to Social Networks. Results show that our method outperforms other state-of-the-art approaches in two out of three of the tested scores within a reasonable amount of time, specially in the important score. Moreover, it is able to obtain near-optimal results when aligning networks with themselves. Furthermore, in larger instances, our algorithm was still able to compete with the best performing method in this regard., Christian Blum and Guillem Rodríguez Corominas, Spain were supported by grants PID2019-104156GB-I00 and TED2021- 129319B-I00 funded by MCIN/AEI/10.13039/501100011033. Maria J. Blesa acknowledges support from AEI, Spain under grant PID2020-112581GB-C21 (MOTION) and the Catalan Agency for Management of University and Research Grants (AGAUR), Spain under grant 2017-SGR-786 (ALBCOM)., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

A logical approach to graph databases

  • Pino Blanco, Elvira
  • Orejas Valdés, Fernando
  • Mylonakis Pascual, Nicolás
  • Pasarella Sánchez, Ana Edelmira
Graph databases are now playing an important role because they allow us to overcome some limitations of relational databases. In particular, in graph databases we are interested not only on the data contained but also on its topology. As a consequence, most graph database queries are navigational, asking whether some nodes are connected by edges or paths. Up to now, most foundational work has concentrated on the study of computational models and query languages, analyzing their expressivity, computability, and complexity. However, in our work we address a different kind of foundational work. We are not concerned with expressibility, efficiency or feasibility issues, but with correctness. More precisely, given an algorithm or an implementation for solving queries, how can we be sure that the answers obtained are correct (soundness) and that all possible correct answers are obtained by our implementation (completeness). In this sense, in this paper we first present a core query language, similar to Cypher or G-Core. Then, we define a simple logic whose formulas are precisely the database queries, and whose satisfaction relation defines what is a correct answer. Finally, we define an operational semantics, which could be seen as an abstract implementation of our language, showing that the semantics is correct, i.e. sound and complete with respect to our logic., Peer Reviewed, Postprint (author's final draft)