Search

Some social networks, such as LinkedIn and ResearchGate, allow user endorsements for specific skills. From the number and quality of the endorsements received, an authority score can be assigned to each profile. In Perez-Roses et al (Proceedings of INNOV 2015: the fourth international conference on communications, computation, networks and technologies, Barcelona, pp. 68---73. http://www.thinkmind.org/index.php?view=instancei Comput Commun 73:200---210. http://dx.doi.org/10.1016/j.comcom.2015.08.018, 2016), an authority score computation method was proposed, which takes into account the relations existing among different skills. The method described in Perez-Roses et al (Proceedings of INNOV 2015: the fourth international conference on communications, computation, networks and technologies, Barcelona, pp 68---73. http://www.thinkmind.org/index.php?view=instancei Comput Commun 73:200---210. http://dx.doi.org/10.1016/j.comcom.2015.08.018, 2016) is based on enriching the digraph of endorsements corresponding to a specific skill, and then applying a ranking method suitable for weighted digraphs, such as PageRank. In this paper we take the method of Perez-Roses et al (Proceedings of INNOV 2015: the fourth international conference on communications, computation, networks and technologies, Barcelona, pp 68---73. http://www.thinkmind.org/index.php?view=instancei Comput Commun 73:200---210. http://dx.doi.org/10.1016/j.comcom.2015.08.018, 2016) to the limit, by successive application of the enrichment step, and we study the mathematical properties of the endorsement digraphs resulting from that process. In particular, we prove that the endorsements converge to some values between 0 and 1, and they reach the value 1 only in some specific circumstances. This allows the use of the limit values as input to the ranking algorithm.

The Degree/diameter problem asks for the largest graphs given diameter and maximum degree. This problem has been extensively studied both for directed and undirected graphs, ando also for special classes of graphs. In this work we present the state of art of the degree/diameter problem for mixed graphs.

The degree diameter problem involves finding the largest graph (in terms of the number of vertices) subject to constraints on the degree and the diameter of the graph. Beyond the degree constraint there is no restriction on the number of edges (apart from keeping the graph simple) so the resulting graph may be thought of as being embedded in the complete graph. In a generalization of this problem, the graph is considered to be embedded in some connected host graph, in this paper the honeycomb network. We consider embedding the graph in the k -dimensional honeycomb grid and provide upper and lower bounds for the optimal graph. The particular cases of dimensions 2 and 3 are examined in detail.

This paper investigates the upper bounds for the number of vertices in mixed abelian Cayley graphs with given degree and diameter. Additionally, in the case when the undirected degree is equal to one, we give a construction that provides a lower bound. The authors have been supported in part by grants MTM2010-21580-C02- 01 and IPT-2102-0603-430000, from Ministerio Español de Economía y Competitividad, and by grant 2009SGR-442, from the Generalitat de Catalunya.

Cayley graphs are well known objects with interesting properties, also in the context of Moore graphs and digraphs. In 1978 Bosak extended Moore's property to the mixed setting (with arcs allowed along with edges), in the so called mixed Moore graphs: those having a unique trail between pairs of vertices at a distance smaller than or equal to the diameter. In this paper we adapt Cayley's construction to mixed graphs and we show certain mixed Moore graphs are Cayley while some other cannot be Cayley.

The Degree/Diameter Problem is an extremal problem in graph theory with applications in network design. One of the main research areas in the Degree/Diameter Problem consists of finding large graphs whose order approach the theoretical upper bounds as much as possible. In the case of directed graphs there exist some families that come close to the theoretical upper bound asymptotically. In the case of undirected graphs there also exist some good constructions for specific values of the parameters involved (degree and/or diameter). One such construction was given by McKay, Miller, and Siraň in [McKay, B., M. Miller and J. Siraň, A note on large graphs of diameter two and given maximum degree, J Comb Theo Ser B 74 (1998), 110-118], which produces large graphs of diameter 2 with the aid of the voltage assignment technique. Here we show how to re-engineer the McKay-Miller-Siraň construction in order to obtain large mixed graphs of diameter 2, i.e. graphs containing both directed arcs and undirected edges.

We give an upper bound for the number of vertices in mixed abelian Cayley graphs with given degree and diameter.

Some social networks, such as LinkedIn and ResearchGate, allow user endorsements for specific skills. In this way, for each skill we get a directed graph where the nodes correspond to users' profiles and the arcs represent endorsement relations. From the number and quality of the endorsements received, an authority score can be assigned to each profile. In this paper we propose an authority score computation method that takes into account the relations existing among different skills. Our method is based on enriching the information contained in the digraph of endorsements corresponding to a specific skill, and then applying a ranking method admitting weighted digraphs, such as PageRank. We describe the method, and test it on a synthetic network of 1493 nodes, fitted with endorsements., Comment: 32 pages

The problem of finding the largest connected subgraph of a given undirected host graph, subject to constraints on the maximum degree @D and the diameter D, was introduced in Dekker et al. (2012) [1], as a generalization of the Degree-Diameter Problem. A case of special interest is when the host graph is a common parallel architecture. Here we discuss the case when the host graph is a k-dimensional mesh. We provide some general bounds for the order of the largest subgraph in arbitrary dimension k, and for the particular cases of k=3,@D=4 and k=2,@D=3, we give constructions that result in sharper lower bounds.

We introduce the problem of finding the largest subgraph of a given weighted undirected graph (host graph), subject to constraints on the maximum degree and the diameter. We discuss some applications in security, network design and parallel processing, and in connection with the latter we derive some bounds for the order of the largest subgraph in host graphs of practical interest: the mesh and the hypercube. We also present a heuristic strategy to solve the problem, and we prove an approximation ratio for the algorithm. Finally, we provide some experimental results with a variety of host networks, which show that the algorithm performs better in practice than the prediction provided by our theoretical approximation ratio.

The degree-diameter problem seeks to find the maximum possible order of a graph with a given (maximum) degree and diameter. It is known that graphs attaining the maximum possible value (the Moore bound) are extremely rare, but much activity is focused on finding new examples of graphs or families of graph with orders approaching the bound as closely as possible. There has been recent interest in this problem as it applies to mixed graphs, in which we allow some of the edges to be undirected and some directed. A 2008 paper of Nguyen and Miller derived an upper bound on the possible number of vertices of such graphs. We show that for diameters larger than three, this bound can be reduced and we present a corrected Moore bound for mixed graphs, valid for all diameters and for all combinations of undirected and directed degrees., 5 pages, 2 figures; amended to remove unnecessary tables

In the pursuit of obtaining largest graphs of given degree and diameter, many construction techniques have arisen. Compounding of graphs is one such technique. In this paper, by means of the compounding of complete graphs into the bipartite Moore graph of diameter 6, we obtain two families of (Δ, 6)-graphs. For maximum degree Δ > 4, being Δ − 1 a prime power, the members of these families constitute the largest known graphs of diameter 6.

In many simulation studies involving networks there is the need to rely on a sample network to perform the simulation experiments. In many cases, real network data is not available due to privacy concerns. In that case we can recourse to synthetic data sets with similar properties to the real data. In this paper we discuss the problem of generating synthetic data sets for a certain kind of online social network, for simulation purposes. Some popular online social networks, such as LinkedIn and ResearchGate, allow user endorsements for specific skills. For each particular skill, the endorsements give rise to a directed subgraph of the corresponding network, where the nodes correspond to network members or users, and the arcs represent endorsement relations. Modelling these endorsement digraphs can be done by formulating an optimization problem, which is amenable to different heuristics. Our construction method consists of two stages: The first one simulates the growth of the network, and the second one solves the aforementioned optimization problem to construct the endorsements., 5 figures, 2 algorithms, Journal of Simulation 2015

Given a tesselation of the plane, defined by a planar straight-line graph G, we want to find a minimal set S of points in the plane, such that the Voronoi diagram associated with S ‘fits’ G. This is the Generalized Inverse Voronoi Problem (GIVP), defined in [12] and rediscovered recently in [3]. Here we give an algorithm that solves this problem with a number of points that is linear in the size of G, assuming that the smallest angle in G is constant.

Augmented Reality systems have recently become widely used. This is due to the new open source libraries that have emerged for fast application development. In this paper we address one of the most relevant problems in this type of systems, oscillation in the camera pose estimates. We study the oscillation of a system developed using the ARToolkit library. We apply both average and Kalman filters to stabilize the estimates. Using filter substantially reduces oscillation, thus improving the system’s usability.

We describe and implement a computer-based method to find large multi-loop graphs with given degree and diameter. For some values of degree and diame- ter, our algorithm produces the largest known circulant graphs. We summarize our findings in a table.

En els últims anys, els mitjans de comunicació han esdevingut un element clau per tal de transmetre informació d'una forma determinada amb l'objectiu de crear una opinió concreta en el lector. Tradicionalment, aquest objectiu s'assolia a través de la pròpia redacció de la informació. No obstant, amb l'aparició de productes interactius on tots els usuaris poden intercanviar informació, ha esdevingut clau la forma en la que aquests usuaris transmeten aquesta informació així com el posicionament que obtenen. Durant aquest treball de fi de màster, s'ha realitzat un seguiment de les notícies publicades a Yahoo! News per tal d'arribar a una aproximació en els seus algorismes de classificació de comentaris. L'objectiu d'aquest treball és poder comprendre quins paràmetres són més importants a l'hora d'establir l'ordre en què els usuaris finals rebran els comentaris publicats, de tal forma que les entitats interessades en aquest aspecte pugin redactar comentaris de forma eficient amb l'objectiu de transmetre una informació determinada. Per tal d'assolir aquest objectiu, en aquest treball s'ha fet ús de metodologies estudiades en aquest màster, tals com els algorismes d'optimització meta-heurística, la programació genètica, les regressions simbòliques, etc. Els resultats d'aquest treball permetran aconseguir una aproximació als algorismes de classificació emprats per Yahoo! News, de tal forma que podrem deduir els criteris seguits amb un determinat error relatiu. Les conclusions d¿aquest treball permetran comprovar que Yahoo! News fa ús de paràmetres de classificació que no es troben a l'abast dels seus usuaris, i que per tant disposa d'una gran opacitat. In recent years, the media has become a key element in conveying information in a certain way with the aim of creating a concrete opinion in the reader.Traditionally, this goal has been achieved through the writing of the information itself. However, with the advent of interactive products where all users can exchange information, it has become key how these users transmit this information as well as the positioning they obtain. During this master's thesis, the news published in Yahoo!News has been trackedin order to arrive at an approximation in their comment classification algorithms.The aim of this work is to be able to understand which parameters are more important when establishing the order in which end users will receive the published comments, so that the entities interested in this aspect can write comments in a way efficient with the aim of transmitting certain information.In order to achieve this goal, in this work we have used methodologies studied in this master's degree, such as meta-heuristic optimization algorithms, genetic programming, symbolic regressions, etc.The results of this work will provide an approximation to the ranking algorithms used by Yahoo!News, so that we can deduce the criteria followed witha certain relative error.The conclusions of this work will allow us to verify that Yahoo!News makes use of classification parameters that are not available to its users, and therefore has a high opacity. En los últimos años, los medios de comunicación han acontecido un elemento clave para transmitir información de una forma determinada con el objetivo de crear una opinión concreta en el lector. Tradicionalmente, este objetivo se lograba a través de la propia redacción de la información. No obstante, con la aparición de productos interactivos donde todos los usuarios pueden intercambiar información, ha acontecido clave la forma en la que estos usuarios transmiten esta información así como el posicionamiento que obtienen. Durante este trabajo de fin de máster, se ha realizado un seguimiento de las noticias publicadas en Yahoo! News para llegar a una aproximación en sus algoritmos de clasificación de comentarios. El objetivo de este trabajo es poder comprender qué parámetros son más importantes en la hora de establecer la orden en que los usuarios finales recibirán los comentarios publicados, de tal forma que las entidades interesadas en este aspecto suban redactar comentarios de forma eficiente con el objetivo de transmitir una información determinada. Para lograr este objetivo, en este trabajo se ha hecho uso de metodologías estudiadas en este máster, tales como los algoritmos de optimización meta-heurística, la programación genética, las regresiones simbólicas, etc. Los resultados de este trabajo permitirán conseguir una aproximación a los algoritmos de clasificación empleados por Yahoo! News, de tal forma que podremos deducir los criterios seguidos con un determinado error relativo. Las conclusiones d¿este trabajo permitirán comprobar que Yahoo! News hace uso de parámetros de clasificación que no se encuentran al alcance de sus usuarios, y que por lo tanto dispone de una gran opacidad.