Search

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)

Un model rellevant en ciència de xarxes són els grafs multicapa, obtinguts per superposició de grafs. En aquest projecte volem portar a terme un estudi experimental de paràmetres i propietats dels grafs geomètrics aleatoris multicapa. Amb l'objectiu d'esbrinar les diferències i similituds en el model a mesura que s'incrementa el nombre de capes, així com altres paràmetres necessaris per generar un graf geomètric aleatori multicapa. Realitzem un estudi sobre una sèrie de paràmetres d'interés obtinguts de generar grans quantitats d'aquest tipus de graf, per tal de veure com progressen modificant aquests atributs generadors, i relacionar els resultats obtinguts a comportaments del camp de les xarxes socials., A relevant model in network science is multilayer graphs, obtained by overlapping graphs. In this project we want to carry out an experimental study of parameters and properties of multilayer random geometric graphs. With the aim of finding out the differences and similarities in the model as the number of layers increases, as well as other parameters necessary to generate a multilayer random geometric graph. We carry out a study on a series of parameters of interest obtained from generating large quantities of this type of graph, in order to see how they progress by modifying these generating attributes, and relate the results obtained to behaviors in the field of social networks.

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

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)

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)

Weighted voting games are simple games that can be represented by a collection of integer weights for each player so that a coalition wins if the sum of the player weights matches or exceeds a given quota. It is known that a simple game can be expressed as the intersection or the union of weighted voting games. The dimension (codimension) of a simple game is the minimum number of weighted voting games such that their intersection (union) is the given game. In this work, we analyze some subclasses of weighted voting games and their closure under intersection or union. We introduce generalized notions of dimension and codimension regarding some subclasses of weighted voting games. In particular, we show that not all simple games can be expressed as intersection (union) of pure weighted voting games (those in which dummy players are not allowed) and we provide a characterization of such simple games. Finally, we experimentally study the generalized dimension (codimension) for some subclasses defined by establishing restrictions on the representations of weighted voting games, Peer Reviewed, Postprint (author's final draft)

Microsoft Active Directory is the default management system for Windows domain networks, so convenient that it is used in many organizations worldwide. Because of this popularity, AD has been a focused cyberattack target. An Active Directory environment could be described as an attack graph in which nodes represent users, computers, groups, and services. The problem is formulated with an attacker who has managed to infiltrate the network to a certain number of nodes (entry nodes) and seeks to reach the most privileged node. On the other hand, the defender's objective will be to maximize the attacker's shortest path length. In this paper, we have conducted a study of the AD-blocking style graph. We have observed that the attack graphs of this Microsoft service have small maximum attack path lengths and are tree-like. The problem is computationally difficult. Six different algorithms have been formulated to solve the problem. Firstly, the problem of blocking only the most vital edge of the attack graph has been investigated, where two algorithms have been formulated and will later become greedy algorithms. An FPT algorithm and three heuristic algorithms have also been developed: a Hill Climbing, a Simulated Annealing, and a genetic algorithm. With these algorithms, we will help IT admins identify high-risk edges in practical Active Directory environments.

The project explains how I have built an hypothesis testing web platform. It has been a mix of knowledge between statistics and software development. I will go briefly over the theory needed (both the distributions that are being used and the kind of tests that I have implemented) as well as explaining the features the platform, how it differentiates itself from other current working solutions and finally explain with all details how it was built.

Fa poc s'han proposat mesures de centralitat per xarxes socials com el FLTR. Aquesta proposta continua l'estudi experimental de la selecció de llindar d'influència en aquesta mesura. En els estudis previs s'han obtingut resultats per algunes xarxes socials. Aquest treball ampliarà l'estudi analitzant diferents mecanismes de selecció de llindar en models de xarxes socials sintètiques., Centrality measures have recently been proposed for social networks, like the FLTR. This proposal continues the experimental study of the influence threshold selection in this measure. Previous studies have obtained results for some social network. This work will expand the study analyzing different threshold selection mechanisms in synthetic social network models.

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

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)

In this paper, we analyze the frequency distributions of weights and quotas in weighted majority voting games (WMVG) up to eight players. We also show different procedures that allow us to obtain some minimum or minimum sum representations of WMVG, for any desired number of players, starting from a minimum or minimum sum representation. We also provide closed formulas for the number of WMVG with n players having a minimum representation with quota up to three, and some subclasses of this family of games. Finally, we complement these results with some upper bounds related to weights and quotas., Peer Reviewed, Postprint (published version)

This project will be focused around the theory of Simple Games, weighted Voting Games will be of special interest and will be extensively studied. In weighted voting games each player is assigned a number called weight which, to some extend, determine how important the player is inside the game, additionally a number named quota determines whether a coalition of players is a winning coalition or not. In this project we focus in two particular representations of weighted voting games, minimum representations and minimum sum representations. The first objective of this project is to obtain throughout small transformations of previously known minimum representations of games, new game representations which still preserve that minimality. Distinct transformations are found that do preserve minimality both, adding new weights and deleting already existing ones. From the generation of new minimum sum games, inequalities aroused relating maximum values of weights and quotas with a fixed amount of players. Another objective of this project was to observe if the distribution of the weights of minimum representations followed a particular probabilistic distribution. Properties of the weights are found and it is shown that as the amount of players increase a smooth probability distribution emerges. Similarly, it was aimed to find the probabilistic distribution that the quotas followed, it will be seen that as the number of players in the game increase a smooth distribution appears again. It was found that, under some circumstances, the distributions of quotas can be counted and listed in a deterministic manner, whenever those circumstances are not achieved, an upper bound of the asymptotic behaviour is given.

We propose the FwLTR and BwLTR, two new centrality measures based on the Linear Threshold model. In contrast to the Linear Threshold rank (LTR), these measures differentiate between the incoming and the outgoing neighborhoods of the activation set that initiates the spreading process. Their rankings are distinguishable from the rest of the centrality measures considered traditionally. However, LTR and BwLTR behave quite similarly, while FwLTR is clearly different., Supported by AEI under grant PID-2020-112581GB-C21 (MOTION) and AGAUR under grant 2017-SGR-786 (ALBCOM)., Peer Reviewed, Postprint (author's final draft)

List k–Coloring (LI k-COL) is the decision problem asking if a given graph admits a proper coloring compatible with a given list assignment to its vertices with colors in {1,2,..., k}. The problem is known to be NP-hard even for k = 3 within the class of 3–regular planar bipartite graphs and for k = 4 within the class of chordal bipartite graphs. In 2015 Huang, Johnson and Paulusma asked for the complexity of LI 3-COL in the class of chordal bipartite graphs. In this paper, we give a partial answer to this question by showing that LI k-COL is polynomial in the class of convex bipartite graphs. We show first that biconvex bipartite graphs admit a multichain ordering, extending the classes of graphs where a polynomial algorithm of Enright, Stewart and Tardos (2014) can be applied to the problem. We provide a dynamic programming algorithm to solve the LI k-COL in the class of convex bipartite graphs. Finally, we show how our algorithm can be modified to solve the more general LI H-COL problem on convex bipartite graphs., J. Díaz and M. Serna are partially supported by funds from MINECO and EU FEDER under grant TIN 2017-86727-C2-1-R AGAUR project ALBCOM 2017- SGR-786. O. Y. Diner is partially supported by the Scientific and Technological Research Council Tubitak under project BIDEB 2219-1059B191802095 and by Kadir Has University under project 2018-BAP-08. O. Serra is supported by the Spanish Ministry of Science under project MTM2017-82166-P., Peer Reviewed, Postprint (author's final draft)

The Slurm Scheduler is a widely used tool for scheduling in High Per- formance Computing platforms around the world. Several studies have been conducted to nd ways to improve speci c performance metrics, mainly from an algorithmic perspective. Scheduling has also been stud- ied from the viewpoint of Game Theory, where models that attempt to capture the main characteristics of the problem are developed and an- alyzed. In this study, we have used the tools that Algorithmic Game Theory provides to develop and study a model that captures some of the main characteristics of the Slurm Scheduler. We developed the necessary software to test these models. We performed a thorough data analysis pro- cess to build a reliable data source based on real usage information. Then, through experimentation, we analyzed how our model and its variants be- have; furthermore, we compared these results with the results from an existing Slurm Simulator, developed by Barcelona Supercomputing Cen- ter members. Using these results, we calculated an approximate value for the Price of Anarchy, and we discuss the Viability of Cooperation in the context of the Slurm Scheduler.

Often, uncertainty is present in processes that are part of our routines. Having tools to understand the consequences of unpredictability is convenient. We introduce a general framework to deal with uncertainty in the realm of distribution sets that are descriptions of imprecise probabilities. We propose several non-biased refinement strategies to obtain sensible forecasts about results of uncertain processes. Initially, uncertainty on a system is modeled as the non-deterministic choice of its possible behaviors. Our refinement hypothesis translates non-determinism into imprecise probabilistic choices. Imprecise probabilities allow us to propose a notion of uncertainty refinement in terms of set inclusions. Later on, unpredictability is tackled through a strategic approach using uncertainty profiles and angel/daemon games ([Formula: see text]-games). Here, imprecise probabilities form the set of mixed strategies and Nash equilibria corresponds to natural uncertainty refinements. We use this approach to study the performance of Web applications — in terms of response times — under stress conditions., J. Castro was partially supported by MINECO and EU FEDER funds grant TIN2017-89244-R and AGAUR grant 2017 SGR-856.J. Gabarro and M. Serna were partially supported by MINECO and EU FEDER funds grant TIN2017-86727-C2-1-R and AGAUR 2017 SGR 786., Peer Reviewed, Postprint (published version)

An influence network is a directed graph with edge weights and node thresholds. Influence spreads starting from X=S. When the sum of the weights of the incoming arcs from X overpasses a node threshold it is added to X. The obtained stable set X=F(S) is the set influenced by S. The Linear Threshold rank is a centrality measure for networks based on this model which measures the influence exerted by a node and its neighbours in the network. The objective is to analyse the effect of the threshold selection in this centrality measure on random social models., Incoming

This research project is an effort towards achieving robot cooperation to complete a set of tasks. The objective is to analyse, compare and explore different reinforcement learning algorithms and see how they perform. This kind of algorithms try to learn from the experience of the robots in an environment. We will go through the formulation of the theory of reinforcement learning, the proofs of the algorithms and the analysis of their behaviour in a concrete domain., Outgoing

El presente proyecto consiste en el diseño y la implementación del software de escritorio de la moto electrica S01 de la marca Silence. Este software interacciona con los distintos elementos de la moto y permite, por una parte, la actualización del firmware de los distintos elementos que conforman el hardware de la moto y, por otra parte, la monitorización de un conjunto de variables con el fin de facilitar al servicio oficial de mantenimiento la prevención y detección de averías. Aunque existen programas estándares para interaccionar con el CAN Bus de vehículos, Silence estaba interesada en crear una interfaz a medida para que pudieran usarla todos los actores implicados en el diseño y fabricación de la moto, así como los servicios oficiales. Aunque inicialmente se iba a desarrollar una única aplicación, basada en otra ya existente para otro modelo anterior escrita Java, se decidió dividir la aplicación en dos aplicaciones que llegaron a denominarse: Monitor y Bootloader. Asímismo se decidió migrar del lenguaje Java a Kotlin. El programa Monitor debe mostrar una serie de información, valores a tiempo real y parámetros de la batería y de la ECU (dos elementos del hardware de la moto) de una forma que resulte útil para el operario que lo use, es decir, usando una interfaz gráfica y sencilla que oculte las dificultades del protocolo CAN. El programa Bootloader sirve para actualizar el firmware de elemento de hardware seleccionado. Todo ello debe hacerse seleccionando la velocidad de transmisión adecuada y con las medidas de seguridad necesarias para abortar el proceso si se produce algún error o la moto no responde., The present project consists in the design and implementation of desktop software for the company Silence's S01 electric scooter. This software interacts with the different elements of the scooter and allows, on the one hand, the firmware update of the different elements that make up the hardware of the scooter and, on the other hand, the monitoring of a set of variables in order to facilitate the prevention and detection of failures to the official maintenance service. Although there are standard programs to interact with CAN Bus, a protocol extensively used in vehicle manufacturing, Silence was interested in creating a custom interface so that all the actors involved in the design and manufacture of the motorcycle could use it, as well as the official services. Although initially it a single application was going to be developed, based on the one that was being used for the previous scooter model and that was written in java, it was decided to divide the application into two applications that came to be called: Monitor and Bootloader. Likewise, it was decided to migrate from the Java language to Kotlin. The Monitor program must show a series of information, real-time values and parameters from the battery and from the ECU (two hardware elements of the scooter) in a way that is useful for the operator who uses it, that is, by using a simple and graphical interface that conceals the difficulties of the CAN protocol. The Bootloader program updates the firmware of a selected hardware element. All this must be done by selecting the appropriate transmission speed and with the necessary security measures to abort the process if an error occurs or the motorcycle does not respond.

Hace poco se han propuesto medidas de centralidad para redes sociales como el FLTR. Este proyecto continúa el estudio experimental de esta medida analizando características de las redes sociales utilizadas, en particular el comportamiento del FLTR bajo diferentes criterios de definición de la resistencia a recibir influencia. En los estudios previos se ha utilizado mayoría simple, nosotros analizamos los casos de pesos aleatorios, definidos por otras medidas de centralidad y otros criterios. También exploramos cuestiones relativas al problema de maximización de la influencia, analizando el potencial de varios conjuntos de actores bajo diversas condiciones.

The aim of this project is to develop efficient algorithms for solving or approximating the Minimum Restricted Linear Coloring Arrangement Problem. It is the first approach to its algorithms, and we will face the problem from different perspectives: constraint programming, backtracking, greedy, and genetic algorithms. As a second goal we are interested in providing theoretical results for particular graphs.

In order to make sound economic decisions it is important to measure the possibilities offered by a market in relation to investments. Provided an investment scheme S = (r; R1, . . . , Rn), where r is a lower bound on the desired investment return and the Ri’s are the asset yields, the power to invest measures the capability of the scheme to fulfill requirement r. The power to invest is inspired in the Coleman’s power of a collectivity to act. We exemplify this approach considering subsets of companies from stock indexes IBEX35 and DAX. We extend the power to invest to investment schemata with imprecise yields. We prove basic relations with the precise yields case and we also show that good monotonicity properties hold. Finally, we propose an analysis, through integrals of the power function, for the case of an unspecific desired return r., Peer Reviewed, Postprint (author's final draft)

Centrality and influence spread are two of the most studied concepts in social network analysis. Several centrality measures, most of them, based on topological criteria, have been proposed and studied. In recent years new centrality measures have been defined inspired by the two main influence spread models, namely, the Independent Cascade Model (IC-model) and the Linear Threshold Model (LT-model). The Linear Threshold Rank (LTR) is defined as the total number of influenced nodes when the initial activation set is formed by a node and its immediate neighbors. It has been shown that LTR allows to rank influential actors in a more distinguishable way than other measures like the PageRank, the Katz centrality, or the Independent Cascade Rank. In this paper we propose a generalized LTR measure that explore the sensitivity of the original LTR, with respect to the distance of the neighbors included in the initial activation set. We appraise the viability of the approach through different case studies. Our results show that by using neighbors at larger distance, we obtain rankings that distinguish better the influential actors. However, the best differentiating ranks correspond to medium distances. Our experiments also show that the rankings obtained for the different levels of neighborhood are not highly correlated, which validates the measure generalization, Peer Reviewed, Postprint (author's final draft)

Nowadays interactions with the World Wide Web are ubiquitous. Users interact through a number of steps consisting of site calls and handling results that can be automatized as orchestrations. Orchestration results have an inherent degree of uncertainty due to incomplete Web knowledge and orchestration semantics are characterized in terms of imprecise probabilistic choices. We consider two aspects in this imprecise semantic characterization. First, when local knowledge (even imprecise) of some part of the Web increases, this knowledge goes smoothly through the whole orchestration. We deal formally with this aspect introducing orchestration refinements. Second, we analyze refinement under uncertainty in the case of parallel composition. Uncertain knowledge is modeled by an uncertainty profile. Such profiles allow us to look at the uncertainty through a zero-sum game, called angel/daemon-game. We propose to use the structure of the Nash equilibria to refine uncertainty. In this case the information improves not through cooperation but through the angel and daemon competition., Peer Reviewed, Postprint (author's final draft)

La centralidad y la difusión de influencia son dos de los conceptos más estudiados en el análisis de redes sociales. La mayoría de medidas de centralidad propuestas, se basan en características topológicas de la red. Recientemente se han propuesto nuevas medidas de centralidad basadas en los dos principales modelos de difusión de influencia, el Independent Cascade Model y el Linear Threshold Model. Una de estas medidas basadas en estos modelos es el Linear Threshold Rank, la cual se define como el numero de nodos influenciados cuando el conjunto de activación inicial es formado por el mismo nodo y sus vecinos inmediatos. En este proyecto, introducimos nuevas medidas de centralidad basadas en esta medida y continuaremos con el análisis de otras medidas basadas en este mismo modelo y en otras variantes de él. Compararemos estas medidas con otras ya conocidas, utilizando diferentes herramientas para el análisis de desigualdad en redes. Propondremos un algoritmo simple y eficiente, para calcularlas, y lo implementaremos en C++ para reducir los tiempos de ejecución. Finalmente, publicaremos los resultados en una plataforma online, para que puedan ser consultados y contrastados fácilmente., Centrality and spread of influence are two of the most studied concepts in the analysis of social networks. Most of the proposed centrality measures are based on topological characteristics of the network. Recently new centrality measures have been proposed inspired by the two main influence spread models, the Independent Cascade Model and the Linear Threshold Model. One of these measures based on these models is the Linear Threshold Rank, which is defined as the number of influenced nodes when the initial activation set is formed by the node itself and its immediate neighbours. In this project, we introduce new centrality measures based on this measure and we will continue with the analysis of other measures based on this same model and other variants of it. We will compare these measures with others already known, using different tools for the analysis of inequality in networks. We will propose a simple and efficient algorithm, to calculate them, and we will implement it in C++ to reduce the execution times. Finally, we will publish the results in an online platform, in order to be easily consulted and contrasted.

We introduce collective decision-making models associated with influence spread under the linear threshold model in social networks. We define the oblivious and the non-oblivious influence models. We also introduce the generalized opinion leader–follower model (gOLF) as an extension of the opinion leader–follower model (OLF) proposed by van den Brink et al. (2011). In our model we allow rules for the final decision different from the simple majority used in OLF. We show that gOLF models are non-oblivious influence models on a two-layered bipartite influence digraph. Together with OLF models, the satisfaction and the power measures were introduced and studied. We analyze the computational complexity of those measures for the decision models introduced in the paper. We show that the problem of computing the satisfaction or the power measure is #P-hard in all the introduced models even when the subjacent social network is a bipartite graph. Complementing this result, we provide two subfamilies of decision models in which both measures can be computed in polynomial time. We show that the collective decision functions are monotone and therefore they define an associated simple game. We relate the satisfaction and the power measures with the Rae index and the Banzhaf value of an associated simple game. This will allow the use of known approximation methods for computing the Banzhaf value, or the Rae index to their practical computation., Peer Reviewed, Postprint (author's final draft)

In this post recession time it is important to measure the possibilities offered by a society in relation to investments. To do that, we consider an investment schema I= (R;R_1,...,R_n) where R is a lower bound on the desired return and the R_i's are the return of the assets (to invest in). We introduce, Peer Reviewed, Postprint (author's final draft)

Un software ha sigut desenvolupat per ajudar en l'anàlisi de segmentacions del genoma, descarregant dades, executant anàlisis i resumint els resultats en una sola visualització que és fàcil d'interpretar i de la qual els investigadors poden extreure hipòtesis biològiques., A software has been developed which helps in the analysis of genome segmentations by automatically downloading data, running analysis and summarizing all results in one single visualization that is easy to read so that researchers can easily conclude biological hypothesis from it.

Centrality and influence spread are two of the most studied concepts in social network analysis. In recent years, centrality measures have attracted the attention of many researchers, generating a large and varied number of new studies about social network analysis and its applications. However, as far as we know, traditional models of influence spread have not yet been exhaustively used to define centrality measures according to the influence criteria. Most of the considered work in this topic is based on the independent cascade model. In this paper we explore the possibilities of the linear threshold model for the definition of centrality measures to be used on weighted and labeled social networks. We propose a new centrality measure to rank the users of the network, the Linear Threshold Rank (LTR), and a centralization measure to determine to what extent the entire network has a centralized structure, the Linear Threshold Centralization (LTC). We appraise the viability of the approach through several case studies. We consider four different social networks to compare our new measures with two centrality measures based on relevance criteria and another centrality measure based on the independent cascade model. Our results show that our measures are useful for ranking actors and networks in a distinguishable way., Peer Reviewed, Postprint (author's final draft)

We propose a model for the behaviour of Web apps in the unreliable WWW. Web apps are described by orchestrations. An orchestration mimics the personal use of the Web by defining the way in which Web services are invoked. The WWW is unreliable as poorly maintained Web sites are prone to fail. We model this source of unreliability trough a probabilistic approach. We assume that each site has a probability to fail. Another source of uncertainty is the traffic congestion. This can be observed as a non-deterministic behaviour induced by the variability in the response times. We model non-determinism by imprecise probabilities. We develop here an ex-ante normal to characterize the behaviour of finite orchestrations in the unreliable Web. We show the existence of a normal form under such semantics for orchestrations using asymmetric parallelism., Peer Reviewed, Postprint (author's final draft)

We consider decision models associated with cooperative influence games, the oblivious and the non-oblivious influence models. In those models the satisfaction and the power measures were introduced and studied. We analyze the computational complexity of those measures when the in uence level is set to unanimity and the rule of decision is simple majority. We show that computing the satisfaction and the power measure in those systems are #P-hard., Peer Reviewed, Postprint (author's final draft)

We propose the use of an angel-daemon framework to perform an uncertainty analysis of short-term macroeconomic models. The angel-daemon framework defines a strategic game where two agents, the angel and the daemon, act selfishly. These games are defined over an uncertainty profile which presents a short and macroscopic description of a perturbed situation. The Nash equilibria on these games provide stable strategies in perturbed situations, giving a natural estimation of uncertainty. We apply the framework to the uncertainty analysis of linear versions of the IS-LM and the IS-MP models., Peer Reviewed, Postprint (author's final draft)

The final publication is available at link.springer.com, We propose the use of the angel-daemon framework to assess the Coleman's power of a collectivity to act under uncertainty in weighted voting games. In this framework uncertainty profiles describe the potential changes in the weights of a weighted game and fixes the spread of the weights' change. For each uncertainty profile a strategic angel-daemon game can be considered. This game has two selfish players, the angel and the daemon, the angel selects its action as to maximize the effect on the measure under consideration while daemon acts oppositely. Players angel and daemon give a balance between the best and the worst. The angel-daemon games associated to the Coleman's power are zero-sum games and therefore the expected utilities of all the Nash equilibria are the same. In this way we can asses the Coleman's power under uncertainty. Besides introducing the framework for this particular setting we analyse basic properties and make some computational complexity considerations. We provide several examples based in the evolution of the voting rules of the EU Council of Ministers., Peer Reviewed, Postprint (author's final draft)

© . This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0, The metric dimension of a graph G is the size of a smallest subset L ¿ V (G) such that for any x, y ¿ V (G) with x =/ y there is a z ¿ L such that the graph distance between x and z differs from the graph distance between y and z. Even though this notion has been part of the literature for almost 40 years, prior to our work the computational complexity of determining the metric dimension of a graph was still very unclear. In this paper, we show tight complexity boundaries for the Metric Dimension problem. We achieve this by giving two complementary results. First, we show that the Metric Dimension problem on planar graphs of maximum degree 6 is NP-complete. Then, we give a polynomial-time algorithm for determining the metric dimension of outerplanar graphs., Peer Reviewed, Postprint (author's final draft)

© . This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0, In this study, we describe a new coordination mechanism for non-atomic congestion games that leads to a (selfish) social cost which is arbitrarily close to the non-selfish optimal. This mechanism incurs no additional cost, in contrast to tolls that typically differ from the social cost as expressed in terms of delays., Peer Reviewed, Postprint (author's final draft)

The final publication is available at link.springer.com, We consider Web services defined by orchestrations in the Orc language and two natural quality of services measures, the number of outputs and a discrete version of the first response time. We analyse first those subfamilies of finite orchestrations in which the measures are well defined and consider their evaluation in both reliable and probabilistic unreliable environments. On those subfamilies in which the QoS measures are well defined, we consider a set of natural related problems and analyse its computational complexity. In general our results show a clear picture of the difficulty of computing the proposed QoS measures with respect to the expressiveness of the subfamilies of Orc. Only in few cases the problems are solvable in polynomial time pointing out the computational difficulty of evaluating QoS measures even in simplified models., Peer Reviewed, Postprint (author's final draft)

The Minimum Linear Colouring Arrangement problem (MinLCA) is a variation from the Minimum Linear Arrangement problem (MinLA) and the Colouring problem. The objective of our problem is finding the best proper colouring of a graph for which the sum of the induced distances between two adjacent vertices is the minimum. In this project, we undertake the task of broadening the previous studies for the MinLCA problem. The main goal is developing some exact algorithms based on backtracking and some heuristic algorithms based on a maximal independent set approach and testing them with different instances of graph families. As a secondary goal we are interested in providing theoretical results for particular graphs. The results will be made available in a simple, open-access benchmarking platform.

In this paper we propose a method to quantitatively analyze the effectiveness of the different measures taken to improve a course’s evaluation process. Our proposal uses simple tools from economics and the social sciences. First, we analyze the effect of these measures on the different categories of grades obtained by the students in relation to the increment of faculty’s workload by means of a marginal cost-benefit approach. In second place, we analyze inequality using different types of data disaggregation in several subpopulations related to the students’ grades. Finally, we study the evolution of statistical indicators such as mean and satisfaction. This method is applied to the study of the CS1 at the Facultat d’Informàtica de Barcelona of the Universitat Politècnica de Catalunya along the first 5 years after the introduction of the new degree in Computer Engineering. The proposed methodology aims to introduce new techniques that allow an objective analysis of the impact of educational measures in any university course., En este trabajo se propone un método para analizar cuantitativamente la efectividad de las diferentes medidas adoptadas para mejorar el proceso de evaluación continua de una asignatura. Nuestra propuesta utiliza herramientas simples provenientes de la economía y de las ciencias sociales. Primero se analiza el efecto de dichas medidas sobre las categorías de calificaciones obtenidas por los estudiantes en relación al incremento de carga docente del profesorado. En el estudio de la evolución de las calificaciones y el trabajo de los profesores a lo largo del tiempo se utiliza una aproximación coste-beneficio marginal. En segundo lugar se realiza un análisis de desigualdad utilizando distintos tipos de desagregación de datos y en varias subpoblaciones relacionadas con las calificaciones de los estudiantes. Finalmente se analiza la evolución de indicadores estadísticos como la media y la satisfacción. Dicho método se aplica al estudio de la asignatura de Programación-1 de la Facultat d’Informàtica de Barcelona de la Universitat Politècnica de Catalunya en los primeros 5 cursos de implantación del Grado en Ingeniería Informática. La metodología propuesta pretende introducir nuevas técnicas que permitan un análisis objetivo del impacto de medidas docentes en cualquier asignatura universitaria., Peer Reviewed, Postprint (published version)

The Generalized Second Price (GSP) auction used typically to model sponsored search auctions does not include the notion of budget constraints, which is present in practice. Motivated by this, we introduce the different variants of GSP auctions that take budgets into account in natural ways. We examine their stability by focusing on the existence of Nash equilibria and envy-free assignments. We highlight the differences between these mechanisms and find that only some of them exhibit both notions of stability. This shows the importance of carefully picking the right mechanism to ensure stable outcomes in the presence of budgets., Peer Reviewed, Postprint (author's final draft)

We introduce Celebrity games, a new model of network creation games. In this model players have weights (W being the sum of all the player's weights) and there is a critical distance ß as well as a link cost a. The cost incurred by a player depends on the cost of establishing links to other players and on the sum of the weights of those players that remain farther than the critical distance. Intuitively, the aim of any player is to be relatively close (at a distance less than ß ) from the rest of players, mainly of those having high weights. The main features of celebrity games are that: computing the best response of a player is NP-hard if ß>1 and polynomial time solvable otherwise; they always have a pure Nash equilibrium; the family of celebrity games having a connected Nash equilibrium is characterized (the so called star celebrity games) and bounds on the diameter of the resulting equilibrium graphs are given; a special case of star celebrity games shares its set of Nash equilibrium profiles with the MaxBD games with uniform bounded distance ß introduced in Bilò et al. [6]. Moreover, we analyze the Price of Anarchy (PoA) and of Stability (PoS) of celebrity games and give several bounds. These are that: for non-star celebrity games PoA=PoS=max{1,W/a}; for star celebrity games PoS=1 and PoA=O(min{n/ß,Wa}) but if the Nash Equilibrium is a tree then the PoA is O(1); finally, when ß=1 the PoA is at most 2. The upper bounds on the PoA are complemented with some lower bounds for ß=2., Peer Reviewed, Postprint (author's final draft)