Deciphering the global organization of clustering in real complex networks

We uncover the global organization of clustering in real complex networks. To this end, we ask whether triangles in real networks organize as in maximally random graphs with given degree and clustering distributions, or as in maximally ordered graph models where triangles are forced into modules. The answer comes by way of exploring m-core landscapes, where the m-core is defined, akin to the k-core, as the maximal subgraph with edges participating in at least m triangles. This property defines a set of nested subgraphs that, contrarily to k-cores, is able to distinguish between hierarchical and modular architectures. We find that the clustering organization in real networks is neither completely random nor ordered although, surprisingly, it is more random than modular. This supports the idea that the structure of real networks may in fact be the outcome of self-organized processes based on local optimization rules, in contrast to global optimization principles.

Manual de gestión documental para el Ayuntamiento de León

En este trabajo se exponen las normas y procedimientos para la implantación en el Ayuntamiento de León de un sistema de gestión documental basado en la norma ISO 15489. Se desarrollan los conceptos básicos para la comprensión del manual, los tipos de documentos administrativos, el uso del lenguaje administrativo, los instrumentos, los diagramas, los formularios y la legislación para llevar a la práctica los sistemas de organización de fondos, clasificación, ordenación, valoración y descripción de documentos y los procesos de instalación, transferencias, régimen de acceso al documento, consultas, préstamos y reproducción de documentos en los archivos de gestión de las oficinas. Palabras clave: Sistema de gestión documental, ISO 15489, Ayuntamiento de León (España), organización de fondos, clasificación de documentos, ordenación de documentos, evaluación de documentos, descripción de documentos, archivos de gestión.

Algoritmos genéticos para la anonimización de grafos

Peer-reviewed

Hybrid model of a double-fed induction machine and back-to-back converter

This report details the port interconnection of two subsystems: a power electronics subsystem (a back-to-back AC/AC converter (B2B), coupled to a phase of the power grid), and an electromechanical subsystem (a doubly-fed induction machine (DFIM), coupled mechanically to a flywheel and electrically to the power grid and to a local varying load). Both subsystems have been essentially described in previous reports (deliverables D 0.5 and D 4.3.1), although some previously unpublished details are presented here. The B2B is a variable structure system (VSS), due to the presence of control-actuated switches: however from a modelling and simulation, as well as a control-design, point of view, it is sensible to consider modulated transformers (MTF in the bond-graph language) instead of the pairs of complementary switches. The port-Hamiltonian models of both subsystems are presents and coupled through a power-preserving interconnection, and the Hamiltonian description of the whole system is obtained; detailed bond-graphs of all the subsystems and the complete system are provided.

Energy-based modelling and simulation of the interconnection of a back-to-back converter and a doubly-fed induction machine

This paper describes the port interconnection of two subsystems: a power electronics subsystem (a back-to-back AC/CA converter (B2B), coupled to a phase of the power grid), and an electromechanical subsystem (a doubly-fed induction machine (DFIM). The B2B is a variable structure system (VSS), due to presence of control-actuated switches: however, from a modelling simulation, as well as a control-design, point of view, it is sensible to consider modulated transformers (MTF in the bond graph language) instead of the pairs of complementary switches. The port-Hamiltonian models of both subsystems are presented and, using a power-preserving interconnection, the Hamiltonian description of the whole system is obtained; detailed bond graphs of all subsystems and the complete system are also provided. Using passivity-based controllers computed in the Hamiltonian formalism for both subsystems, the whole model is simulated; simulations are run to rest the correctness and efficiency of the Hamiltonian network modelling approach used in this work.

Artificial evolution on network structures : how time and space influence dynamics

Abstract The main objective of this work is to show how the choice of the temporal dimension and of the spatial structure of the population influences an artificial evolutionary process. In the field of Artificial Evolution we can observe a common trend in synchronously evolv¬ing panmictic populations, i.e., populations in which any individual can be recombined with any other individual. Already in the '90s, the works of Spiessens and Manderick, Sarma and De Jong, and Gorges-Schleuter have pointed out that, if a population is struc¬tured according to a mono- or bi-dimensional regular lattice, the evolutionary process shows a different dynamic with respect to the panmictic case. In particular, Sarma and De Jong have studied the selection pressure (i.e., the diffusion of a best individual when the only selection operator is active) induced by a regular bi-dimensional structure of the population, proposing a logistic modeling of the selection pressure curves. This model supposes that the diffusion of a best individual in a population follows an exponential law. We show that such a model is inadequate to describe the process, since the growth speed must be quadratic or sub-quadratic in the case of a bi-dimensional regular lattice. New linear and sub-quadratic models are proposed for modeling the selection pressure curves in, respectively, mono- and bi-dimensional regu¬lar structures. These models are extended to describe the process when asynchronous evolutions are employed. Different dynamics of the populations imply different search strategies of the resulting algorithm, when the evolutionary process is used to solve optimisation problems. A benchmark of both discrete and continuous test problems is used to study the search characteristics of the different topologies and updates of the populations. In the last decade, the pioneering studies of Watts and Strogatz have shown that most real networks, both in the biological and sociological worlds as well as in man-made structures, have mathematical properties that set them apart from regular and random structures. In particular, they introduced the concepts of small-world graphs, and they showed that this new family of structures has interesting computing capabilities. Populations structured according to these new topologies are proposed, and their evolutionary dynamics are studied and modeled. We also propose asynchronous evolutions for these structures, and the resulting evolutionary behaviors are investigated. Many man-made networks have grown, and are still growing incrementally, and explanations have been proposed for their actual shape, such as Albert and Barabasi's preferential attachment growth rule. However, many actual networks seem to have undergone some kind of Darwinian variation and selection. Thus, how these networks might have come to be selected is an interesting yet unanswered question. In the last part of this work, we show how a simple evolutionary algorithm can enable the emrgence o these kinds of structures for two prototypical problems of the automata networks world, the majority classification and the synchronisation problems. Synopsis L'objectif principal de ce travail est de montrer l'influence du choix de la dimension temporelle et de la structure spatiale d'une population sur un processus évolutionnaire artificiel. Dans le domaine de l'Evolution Artificielle on peut observer une tendence à évoluer d'une façon synchrone des populations panmictiques, où chaque individu peut être récombiné avec tout autre individu dans la population. Déjà dans les année '90, Spiessens et Manderick, Sarma et De Jong, et Gorges-Schleuter ont observé que, si une population possède une structure régulière mono- ou bi-dimensionnelle, le processus évolutionnaire montre une dynamique différente de celle d'une population panmictique. En particulier, Sarma et De Jong ont étudié la pression de sélection (c-à-d la diffusion d'un individu optimal quand seul l'opérateur de sélection est actif) induite par une structure régulière bi-dimensionnelle de la population, proposant une modélisation logistique des courbes de pression de sélection. Ce modèle suppose que la diffusion d'un individu optimal suit une loi exponentielle. On montre que ce modèle est inadéquat pour décrire ce phénomène, étant donné que la vitesse de croissance doit obéir à une loi quadratique ou sous-quadratique dans le cas d'une structure régulière bi-dimensionnelle. De nouveaux modèles linéaires et sous-quadratique sont proposés pour des structures mono- et bi-dimensionnelles. Ces modèles sont étendus pour décrire des processus évolutionnaires asynchrones. Différentes dynamiques de la population impliquent strategies différentes de recherche de l'algorithme résultant lorsque le processus évolutionnaire est utilisé pour résoudre des problèmes d'optimisation. Un ensemble de problèmes discrets et continus est utilisé pour étudier les charactéristiques de recherche des différentes topologies et mises à jour des populations. Ces dernières années, les études de Watts et Strogatz ont montré que beaucoup de réseaux, aussi bien dans les mondes biologiques et sociologiques que dans les structures produites par l'homme, ont des propriétés mathématiques qui les séparent à la fois des structures régulières et des structures aléatoires. En particulier, ils ont introduit la notion de graphe sm,all-world et ont montré que cette nouvelle famille de structures possède des intéressantes propriétés dynamiques. Des populations ayant ces nouvelles topologies sont proposés, et leurs dynamiques évolutionnaires sont étudiées et modélisées. Pour des populations ayant ces structures, des méthodes d'évolution asynchrone sont proposées, et la dynamique résultante est étudiée. Beaucoup de réseaux produits par l'homme se sont formés d'une façon incrémentale, et des explications pour leur forme actuelle ont été proposées, comme le preferential attachment de Albert et Barabàsi. Toutefois, beaucoup de réseaux existants doivent être le produit d'un processus de variation et sélection darwiniennes. Ainsi, la façon dont ces structures ont pu être sélectionnées est une question intéressante restée sans réponse. Dans la dernière partie de ce travail, on montre comment un simple processus évolutif artificiel permet à ce type de topologies d'émerger dans le cas de deux problèmes prototypiques des réseaux d'automates, les tâches de densité et de synchronisation.

Coneixements i usos lingüístics de l'estudiantat de la Universitat de Lleida (2012 / 2013). Estudi comparatiu dels resultats obtinguts el 1993/1994 amb els de l’actualitat

El treball que teniu a les mans és una recerca sociolingüística que té com a objectiu l’anàlisi dels coneixements i els usos lingüístics de la Universitat de Lleida, a partir de la comparació dels resultats obtinguts a “Coneixements i usos lingüístics de l’estudiantat de la Universitat de Lleida” (Curs 1993/1994), un estudi impulsat des dels Servei de Llengua i Terminologia l’any 1993. L’elaboració del treball es divideix en tres etapes: l’etapa d’investigació, l’etapa d’organització i l’etapa d’interpretació. La primera etapa ha estat destinada a la recollida de dades. He demanat a un total de 1046 alumnes provinents de vint-i-un graus o especialitat diferents que contestessin un qüestionari. La segona etapa consisteix en l’organització de les dades. El primer que he fet ha estat entrar els resultats de cadascuna de les enquestes al programa ACCES, el qual m’ha permès fer les posteriors agrupacions partint sempre del model de 1993. Una vegada he tingut totes les agrupacions fetes, he fet tots els percentatges, gràfiques i taules al programa Excel. Finalment, quan ja he tingut tots els gràfics i taules confeccionats he passat ja a l’última etapa del treball: la interpretació de les dades. Primer he fet una lectura de cadascun dels gràfics i taules, comparant-los posteriorment amb els resultats obtinguts el 1993. Una vegada he tingut tots els comentaris fets he passat ja al més important: la redacció de les conclusions, on intento explicar els canvis més importants que he copsat.

On balanced CSPs with high treewidth

Tractable cases of the binary CSP are mainly divided in two classes: constraint language restrictions and constraint graph restrictions. To better understand and identify the hardest binary CSPs, in this work we propose methods to increase their hardness by increasing the balance of both the constraint language and the constraint graph. The balance of a constraint is increased by maximizing the number of domain elements with the same number of occurrences. The balance of the graph is defined using the classical definition from graph the- ory. In this sense we present two graph models; a first graph model that increases the balance of a graph maximizing the number of vertices with the same degree, and a second one that additionally increases the girth of the graph, because a high girth implies a high treewidth, an important parameter for binary CSPs hardness. Our results show that our more balanced graph models and constraints result in harder instances when compared to typical random binary CSP instances, by several orders of magnitude. Also we detect, at least for sparse constraint graphs, a higher treewidth for our graph models.

A note on the periodic orbits and topological entropy of graph maps

This paper deals with the relationship between the periodic orbits of continuous maps on graphs and the topological entropy of the map. We show that the topological entropy of a graph map can be approximated by the entropy of its periodic orbits.

Reporting for account and sales management

Tutkimuksen tavoitteena oli kerätä Elcoteq Network Oyj:n myyntihenkilöiden tietotarpeet ja konkretisoida ne raportoinnin kautta. Tutkimus keskittyi asiakasvirran eri vaiheissa tarvittavaan asiakas- ja projektikohtaiseen tietoon. Tarkoituksena oli parantaa raportointia vastaamaan asiakkaan ja sales case:n hallintaa alkaen asiakasvirran uusasiakasvaiheesta ja projektin arvioinnista. Tietotarpeet kerättiin haastattelujen avulla ja osallistumalla aiheeseen liittyviin projekteihin. Haastattelujen ja teorian avulla projektiliiketoiminnan avainpiirteet ja asiakaskannattavuuteen vaikuttavat tekijät kerättiin yhteen ja muutettiin konkretiaksi raportoinnin parannusehdotuksien kautta. Tutkimus osoitti, että myyntihenkilöiden näkökulmasta olisi muodostettava uudet raportit tukemaan asiakkaan ja projektin hallintaa. Ennustettu voidaan verrata toteutuneeseen ja sekä asikkuuden, että sales case:n seuranta paranee uusien raporttien avulla. Budjetit, sekä asiakaskohtaiset tavoitteet voidaan laatia luotettavimmin ja kokonaiskuva asiakkuuden ja projektin kannattavuudesta pystytään näkemään ko. raporteista sekä graafein, että numeerisena tietona.

Sherali-Adams Relaxations and Indistinguishability in Counting Logics

Two graphs with adjacency matrices $\mathbf{A}$ and $\mathbf{B}$ are isomorphic if there exists a permutation matrix $\mathbf{P}$ for which the identity $\mathbf{P}^{\mathrm{T}} \mathbf{A} \mathbf{P} = \mathbf{B}$ holds. Multiplying through by $\mathbf{P}$ and relaxing the permutation matrix to a doubly stochastic matrix leads to the linear programming relaxation known as fractional isomorphism. We show that the levels of the Sherali--Adams (SA) hierarchy of linear programming relaxations applied to fractional isomorphism interleave in power with the levels of a well-known color-refinement heuristic for graph isomorphism called the Weisfeiler--Lehman algorithm, or, equivalently, with the levels of indistinguishability in a logic with counting quantifiers and a bounded number of variables. This tight connection has quite striking consequences. For example, it follows immediately from a deep result of Grohe in the context of logics with counting quantifiers that a fixed number of levels of SA suffice to determine isomorphism of planar and minor-free graphs. We also offer applications in both finite model theory and polyhedral combinatorics. First, we show that certain properties of graphs, such as that of having a flow circulation of a prescribed value, are definable in the infinitary logic with counting with a bounded number of variables. Second, we exploit a lower bound construction due to Cai, Fürer, and Immerman in the context of counting logics to give simple explicit instances that show that the SA relaxations of the vertex-cover and cut polytopes do not reach their integer hulls for up to $\Omega(n)$ levels, where $n$ is the number of vertices in the graph.

Sobre o condicionamento alimentar na cochonilha-branca, Planococcus citri (Risso) (Hemiptera: pseudococcidae)

Estudos do comportamento alimentar mediante a técnica de "Electrical Penetration Graphs" (EPG) das cochonilhas-farinhentas (Pseudococcidae) provenientes de um hospedeiro de criação alternativo têm mostrado que esses insetos não atingem ou demoram cerca de 9 horas para alcançar a fase floemática. Por outro lado, aqueles provenientes do hospedeiro-fonte atingem a fase floemática mais rapidamente e apresentam maior frequência de alimentação nos vasos crivados. Esses resultados indicam a presença do fenômeno de condicionamento alimentar, ainda não demonstrado em cochonilhas. Assim, o presente trabalho teve como objetivo determinar a existência desse fenômeno em Planococcus citri (Risso) (Hemiptera: Pseudococcidae). Foram realizados testes de livre escolha, monitoramento eletrônico (EPG) e estudos de alguns parâmetros biológicos. Em todos os experimentos, o cafeeiro (Coffea arabica L.), os citros (Citrus sinensis L.) e abóbora (Cucurbita maxima L.) foram utilizados como substratos de criação (fonte) da cochonilha, sendo os tratamentos constituídos pela combinação entre os hospedeiros-fonte e os hospedeiros receptores (café e citros). O teste de escolha entre cafeeiro e citros nas primeiras 72 horas mostrou que as cochonilhas criadas em cafeeiro apresentaram preferência pelo cafeeiro; aquelas originadas dos citros mostraram uma tendência, embora não significativa, em selecionar os citros em relação ao cafeeiro e aquelas criadas em abóbora não mostraram preferência por nenhum dos hospedeiros. Os estudos do comportamento alimentar mediante o monitoramento eletrônico (EPG) mostraram que a fase floemática, considerada como a fase de aceitação do hospedeiro, foi mais frequente em cafeeiro, seja com cochonilhas oriundas deste substrato, seja de citros. Aqueles insetos mantidos em abóbora e transferidos para o cafeeiro ou citros apresentaram excepcionalmente ou não apresentaram nenhuma fase floemática, respectivamente. A transferência de cochonilhas de qualquer hospedeiro-fonte para cafeeiro ou citros não afetou o tempo de desenvolvimento, fecundidade e mortalidade, porém aquelas criadas e mantidas em abóbora mostraram maior fecundidade quando comparadas com qualquer outro substrato receptor. Conclui-se que a transferência do substrato, seja cafeeiro, seja citros, não influencia significativamente o comportamento alimentar e o desenvolvimento de P. citri, embora possa existir preferência inicial pelo hospedeiro-fonte.

Development of the Simulation Environment for the Mobile Phone User Interfaces

Diplomityössä käsitellään Nokia Mobile Phonesin matkapuhelimien käyttöliittymäohjelmistojen suunnittelu-ja testausympäristön kehitystä. Ympäristöön lisättiin kaksi ohjelmistomodulia avustamaan simulointia ja versionhallintaa. Visualisointityökalulla matkapuhelimen toiminta voidaan jäljittää suunnittelu- kaavioihin tilasiirtyminä, kun taas vertailusovelluksella kaavioiden väliset erot nähdään graafisesti. Kehitetyt sovellukset parantavat käyttöliittymien suunnitteluprosessia tehostaen virheiden etsintää, optimointia ja versionhallintaa. Visualisointityökalun edut ovat merkittävät, koska käyttöliittymäsovellusten toiminta on havaittavissa suunnittelu- kaavioista reaaliaikaisen simuloinnin yhteydessä. Näin virheet ovat välittömästi paikannettavissa. Lisäksi työkalua voidaan hyödyntää kaavioita optimoitaessa, jolloin sovellusten kokoja muistintarve pienenee. Graafinen vertailutyökalu tuo edun rinnakkaiseen ohjelmistosuunnitteluun. Eri versioisten suunnittelukaavioiden erot ovat nähtävissä suoraan kaaviosta manuaalisen vertailun sijaan. Molemmat työkalut otettiin onnistuneesti käyttöön NMP:llä vuoden 2001 alussa.

Statistical mechanics of multi-edge networks

Statistical properties of binary complex networks are well understood and recently many attempts have been made to extend this knowledge to weighted ones. There are, however, subtle yet important considerations to be made regarding the nature of the weights used in this generalization. Weights can be either continuous or discrete magnitudes, and in the latter case, they can additionally have undistinguishable or distinguishable nature. This fact has not been addressed in the literature insofar and has deep implications on the network statistics. In this work we face this problem introducing multiedge networks as graphs where multiple (distinguishable) connections between nodes are considered. We develop a statistical mechanics framework where it is possible to get information about the most relevant observables given a large spectrum of linear and nonlinear constraints including those depending both on the number of multiedges per link and their binary projection. The latter case is particularly interesting as we show that binary projections can be understood from multiedge processes. The implications of these results are important as many real-agent-based problems mapped onto graphs require this treatment for a proper characterization of their collective behavior.