Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?

Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.

Découvrez-en plus sur les applications Graph.

Graph
Search

fr|en

Se Connecter

Concept

Graphe de Petersen

Résumé

Le graphe de Petersen est, en théorie des graphes, un graphe particulier possédant et . Il s'agit d'un petit graphe qui sert d'exemple et de contre-exemple pour plusieurs problèmes de la théorie des graphes. Il porte le nom du mathématicien Julius Petersen, qui l'introduisit en 1898 en tant que plus petit graphe cubique sans isthme dont les arêtes ne peuvent être colorées avec trois couleurs. Il a cependant été mentionné par Alfred Kempe pour la première fois auparavant, en 1886. Donald Knuth explique dans The Art of Computer Programming que le graphe de Petersen est . Constructions Le graphe de Petersen est le complémentaire du line graph du graphe complet K_5. C'est également le graphe de Kneser KG_{5,2} ; il est donc possible de construire le graphe de Petersen en considérant un sommet pour chaque couple d'un ensemble de 5 éléments, et en reliant deux sommets si les couples correspondants sont disjoints. Géométriquement, le graphe de Pete

Source officielle

https://fr.wikipedia.org/wiki/Graphe_de_Petersen

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées (4)

Publications associées

Chargement

Personnes associées

Chargement

Unités associées

Chargement

Concepts associés (21)

Concepts associés

Chargement

Cours associés (3)

Cours associés

Chargement

Séances de cours associées (3)

Séances de cours associées

Chargement

Over recent years, many large network datasets become available, giving rise to novel and valuable applications of data mining and machine learning techniques. These datasets include social networks, the structure of the Internet, and protein-interaction networks, to name just a few. Graph mining exploits information hidden in these data to shed light on such problems as finding relevant pages on the web, or identifying communities of strongly connected individuals. Clearly, to address such problems, we first need the complete and reliable network graph. In many real-world scenarios, the full graph is not available for free. For example, data-collection processes may be noisy and unreliable or node identifiers may be hidden for privacy protection. Therefore, we cannot rely on the node labels to infer the full graph. In this thesis, we address fundamental and practical questions of inferring a true full network from multiple ambiguous observations. We formulate two variations of this problem: network alignment and network assembly. In each variant, we address two types of questions: first, we characterize how graph features impact the fundamental feasibility of reconstruction; second, we seek efficient algorithms that can scale to very large networks. In the first part of this thesis, we consider network alignment. We assume two large, noisy observations of the true network that are not labeled. Network alignment refers to the problem of aligning the vertices of the two networks using only structural cues and it can be viewed as a generalization of the classic graph-isomorphism problem. We make the following contributions. First, we introduce a random bigraph model with parameters p, t and s that generates two correlated graphs. We characterize conditions on p, t and s for the feasibility of alignment of two graphs. Second, we create an algorithm named percolation graph-matching (PGM) that builds an alignment from a small set of pre-matched nodes S. We prove conditions on the parameters p, t , s and r for which PGM succeeds, and we establish a phase transition in |S|. In the second part of this thesis, we consider network assembly. We assume many small, noisy observations of the true network, called patches. The node labels are either absent or not unique. The network assembly problem consists in reconstructing the true graph from these patches. We make the following contributions. First, we introduce a novel random-graph model with parameters p and q that generates a network with high clustering. We characterize conditions on p and q for feasibility of assembly. Second, we propose a heuristic assembly algorithm to reconstruct the true graph from arbitrary patches with label ambiguity.

EPFL2017

Chargement

Assembling a Network out of Ambiguous Patches

Jefferson Elbert Simões, Matthias Grossglauser, Lyudmila Yartseva

Many graph mining and network analysis problems rely on the availability of the full network over a set of nodes. But inferring a full network is sometimes non-trivial if the raw data is in the form of many small {\em patches} or subgraphs, of the true network, and if there are ambiguities in the identities of nodes or edges in these patches. This may happen because of noise or because of the nature of data; for instance, in social networks, names are typically not unique. \textit{Graph assembly} refers to the problem of reconstructing a graph from these many, possibly noisy, partial observations. Prior work suggests that graph assembly is essentially impossible in regimes of interest when the true graph is Erdos-Renyi. The purpose of the present paper is to show that a modest amount of clustering is sufficient to assemble even very large graphs. We introduce the

G(n,p;q)

random graph model, which is the random closure over all open triangles of a

G(n,p)

Erdos-Renyi, and show that this model exhibits higher clustering than an equivalent Erdos-Renyi. We focus on an extreme case of graph assembly: the patches are small (

1

-hop egonets) and are unlabeled. We show that in realistic regimes, graph assembly is fundamentally feasible, because we can identify, for every edge

e

, a subgraph induced by its neighbors that is unique and present in every patch containing

e

. Using this result, we build a practical algorithm that uses canonical labeling to reconstruct the original graph from noiseless patches. We also provide an achievability result for noisy patches, which are obtained by edge-sampling the original egonets.

2016

Chargement

Independence number of generalized Petersen graphs

Javad Ebrahimi Boroojeni

Determining the size of a maximum independent set of a graph G, denoted by alpha(G), is an NP-hard problem. Therefore many attempts are made to find upper and lower bounds, or exact values of alpha(G) for special classes of graphs. This paper is aimed toward studying this problem for the class of generalized Petersen graphs. We find new upper and lower bounds and some exact values for alpha(P(n, k)). With a computer program we have obtained exact values for each n < 78. In [2] it is conjectured that the size of the minimum vertex cover, beta(P(n, k)), is less than or equal to n + inverted right perpendicular n/5 inverted left perpendicular, for all n and k with n > 2k. We prove this conjecture for some cases. In particular, we show that if n > 3k, the conjecture is valid. We checked the conjecture with our table for n < 78 and it had no inconsistency. Finally, we show that for every fixed k, alpha(P(n,k)) can be computed using an algorithm with running time O(n).

Charles Babbage Res Ctr2016

Chargement

Assembling a Network out of Ambiguous Patches

Jefferson Elbert Simões, Matthias Grossglauser, Lyudmila Yartseva

G(n,p;q)

random graph model, which is the random closure over all open triangles of a

G(n,p)

Erdos-Renyi, and show that this model exhibits higher clustering than an equivalent Erdos-Renyi. We focus on an extreme case of graph assembly: the patches are small (

1

-hop egonets) and are unlabeled. We show that in realistic regimes, graph assembly is fundamentally feasible, because we can identify, for every edge

e

, a subgraph induced by its neighbors that is unique and present in every patch containing

e

2016

EPFL2017