On The Center Sets and Center Numbers of Some Graph Classes

For a set S of vertices and the vertex v in a connected graph G, max x2S d(x, v) is called the S-eccentricity of v in G. The set of vertices with minimum S-eccentricity is called the S-center of G. Any set A of vertices of G such that A is an S-center for some set S of vertices of G is called a center set. We identify the center sets of certain classes of graphs namely, Block graphs, Km,n, Kn −e, wheel graphs, odd cycles and symmetric even graphs and enumerate them for many of these graph classes. We also introduce the concept of center number which is defined as the number of distinct center sets of a graph and determine the center number of some graph classes

Iceberg query lattices for datalog

In this paper we study two orthogonal extensions of the classical data mining problem of mining association rules, and show how they naturally interact. The first is the extension from a propositional representation to datalog, and the second is the condensed representation of frequent itemsets by means of Formal Concept Analysis (FCA). We combine the notion of frequent datalog queries with iceberg concept lattices (also called closed itemsets) of FCA and introduce two kinds of iceberg query lattices as condensed representations of frequent datalog queries. We demonstrate that iceberg query lattices provide a natural way to visualize relational association rules in a non-redundant way.

Understanding Subsystems in Biology through Dimensionality Reduction, Graph Partitioning and Analytical Modeling

Biological systems exhibit rich and complex behavior through the orchestrated interplay of a large array of components. It is hypothesized that separable subsystems with some degree of functional autonomy exist; deciphering their independent behavior and functionality would greatly facilitate understanding the system as a whole. Discovering and analyzing such subsystems are hence pivotal problems in the quest to gain a quantitative understanding of complex biological systems. In this work, using approaches from machine learning, physics and graph theory, methods for the identification and analysis of such subsystems were developed. A novel methodology, based on a recent machine learning algorithm known as non-negative matrix factorization (NMF), was developed to discover such subsystems in a set of large-scale gene expression data. This set of subsystems was then used to predict functional relationships between genes, and this approach was shown to score significantly higher than conventional methods when benchmarking them against existing databases. Moreover, a mathematical treatment was developed to treat simple network subsystems based only on their topology (independent of particular parameter values). Application to a problem of experimental interest demonstrated the need for extentions to the conventional model to fully explain the experimental data. Finally, the notion of a subsystem was evaluated from a topological perspective. A number of different protein networks were examined to analyze their topological properties with respect to separability, seeking to find separable subsystems. These networks were shown to exhibit separability in a nonintuitive fashion, while the separable subsystems were of strong biological significance. It was demonstrated that the separability property found was not due to incomplete or biased data, but is likely to reflect biological structure.

Web Graph

Slides and an essay on the Web Graph, search engines and how Google calculates Page Rank

Graph Theory and Social Networks Tutorial

For COMP60

Análisis de los efectos económicos y socio-políticos en Chile de la tradición exportadora minera y del TLC entre China y Chile, en especial para el período 2006-2012

Esta monografía pretende evaluar los efectos de la tradición exportadora minera y el TLC entre China y Chile desde las perspectivas de violencia estructural y desarrollo como libertad de Amartya Sen y Johan Galtung, respectivamente. A través del análisis de algunos procesos históricos que han configurado las actuales dinámicas mineras y comerciales en Chile, y de las libertades reales que poseían los chilenos antes y después de la entrada en vigor del acuerdo, se logra comprender la manera en la que los fenómenos estudiados logran constreñir o impulsar el desarrollo de las capacidades de los chilenos para llevar a cabo las vidas que desean.

Speak to me graph.

Se compone de diez actividades destinadas a ayudar a los profesores a desarrollar las capacidades de análisis e interpretación de datos de los alumnos de ciencias. Cada actividad incluye una hoja de preguntas y una hoja de datos, ésta última, disponible en archivos de Excel, para que los estudiantes utilicen las nuevas tecnologías para crear gráficos. Los ejercicios están pensados para el nivel superior de la etapa 2 (key stage 2) del currículo nacional inglés y para la etapa 3, es decir, para primaria y secundaria, y se centran en el contenido de 'Sc2 Life and Living Proceses'.

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