Equal opportunity networks, distance-balanced graphs, and Wiener game

Given a graph G and a set X ⊆ V(G), the relative Wiener index of X in G is defined as WX (G) = {u,v}∈X 2  dG(u, v) . The graphs G (of even order) in which for every partition V(G) = V1 +V2 of the vertex set V(G) such that |V1| = |V2| we haveWV1 (G) = WV2 (G) are called equal opportunity graphs. In this note we prove that a graph G of even order is an equal opportunity graph if and only if it is a distance-balanced graph. The latter graphs are known by several characteristic properties, for instance, they are precisely the graphs G in which all vertices u ∈ V(G) have the same total distance DG(u) = v∈V(G) dG(u, v). Some related problems are posed along the way, and the so-called Wiener game is introduced.

Betweenness Centrality in Some Classes of Graphs

There are several centrality measures that have been introduced and studied for real world networks. They account for the different vertex characteristics that permit them to be ranked in order of importance in the network. Betweenness centrality is a measure of the influence of a vertex over the flow of information between every pair of vertices under the assumption that information primarily flows over the shortest path between them. In this paper we present betweenness centrality of some important classes of graphs.

Mathematical Morphology on Hypergraphs Using Vertex-Hyperedge Correspondence

The focus of this paper is to develop computationally efficient mathematical morphology operators on hypergraphs. To this aim we consider lattice structures on hypergraphs on which we build morphological operators. We develop a pair of dual adjunctions between the vertex set and the hyperedge set of a hypergraph , by defining a vertex-hyperedge correspondence. This allows us to recover the classical notion of a dilation/erosion of a subset of vertices and to extend it to subhypergraphs of . This paper also studies the concept of morphological adjunction on hypergraphs for which both the input and the output are hypergraphs

Fair Sets of Some Classes of Graphs

Given a non empty set S of vertices of a graph, the partiality of a vertex with respect to S is the di erence between maximum and minimum of the distances of the vertex to the vertices of S. The vertices with minimum partiality constitute the fair center of the set. Any vertex set which is the fair center of some set of vertices is called a fair set. In this paper we prove that the induced subgraph of any fair set is connected in the case of trees and characterise block graphs as the class of chordal graphs for which the induced subgraph of all fair sets are connected. The fair sets of Kn, Km;n, Kn e, wheel graphs, odd cycles and symmetric even graphs are identi ed. The fair sets of the Cartesian product graphs are also discussed

Content aggregation on knowledge bases using graph clustering

Recently, research projects such as PADLR and SWAP have developed tools like Edutella or Bibster, which are targeted at establishing peer-to-peer knowledge management (P2PKM) systems. In such a system, it is necessary to obtain provide brief semantic descriptions of peers, so that routing algorithms or matchmaking processes can make decisions about which communities peers should belong to, or to which peers a given query should be forwarded. This paper proposes the use of graph clustering techniques on knowledge bases for that purpose. Using this clustering, we can show that our strategy requires up to 58% fewer queries than the baselines to yield full recall in a bibliographic P2PKM scenario.

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

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

Using the web graph to influence application behaviour

The Web's link structure (termed the Web Graph) is a richly connected set of Web pages. Current applications use this graph for indexing and information retrieval purposes. In contrast the relationship between Web Graph and application is reversed by letting the structure of the Web Graph influence the behaviour of an application. Presents a novel Web crawling agent, AlienBot, the output of which is orthogonally coupled to the enemy generation strategy of a computer game. The Web Graph guides AlienBot, causing it to generate a stochastic process. Shows the effectiveness of such unorthodox coupling to both the playability of the game and the heuristics of the Web crawler. In addition, presents the results of the sample of Web pages collected by the crawling process. In particular, shows: how AlienBot was able to identify the power law inherent in the link structure of the Web; that 61.74 per cent of Web pages use some form of scripting technology; that the size of the Web can be estimated at just over 5.2 billion pages; and that less than 7 per cent of Web pages fully comply with some variant of (X)HTML.