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): 60
Encontrada(s) 1 página(s)

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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

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

  • 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 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, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
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
  • 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, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

The diameter of sum basic equilibria games

  • Abiad Monge, Aida
  • Álvarez Faura, M. del Carme
  • Messegué Buisan, Arnau
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, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Mathematical models to describe fixation disparity curves

  • Argilés Sans, Marc
  • Molinero Albareda, Xavier
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, Postprint (published version)