Academic literature on the topic 'Graphe biparti'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Graphe biparti.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Journal articles on the topic "Graphe biparti"
1
KIYOMI, MASASHI, TOSHIKI SAITOH, and RYUHEI UEHARA. "BIPARTITE PERMUTATION GRAPHS ARE RECONSTRUCTIBLE." Discrete Mathematics, Algorithms and Applications 04, no. 03 (August 6, 2012): 1250039. http://dx.doi.org/10.1142/s1793830912500395.
Full textAbstract:
The graph reconstruction conjecture is a long-standing open problem in graph theory. The conjecture has been verified for all graphs with at most 11 vertices. Further, the conjecture has been verified for regular graphs, trees, disconnected graphs, unit interval graphs, separable graphs with no pendant vertex, outer-planar graphs, and unicyclic graphs. We extend the list of graph classes for which the conjecture holds. We give a proof that bipartite permutation graphs are reconstructible.
2
Farooq, Rashid, Mehar Ali Malik, Qudsia Naureen, and Shariefuddin Pirzada. "On the nullity of a family of tripartite graphs." Acta Universitatis Sapientiae, Informatica 8, no. 1 (June 1, 2016): 96–107. http://dx.doi.org/10.1515/ausi-2016-0006.
Full textAbstract:
Abstract The eigenvalues of the adjacency matrix of a graph form the spectrum of the graph. The multiplicity of the eigenvalue zero in the spectrum of a graph is called nullity of the graph. Fan and Qian (2009) obtained the nullity set of n-vertex bipartite graphs and characterized the bipartite graphs with nullity n − 4 and the regular n-vertex bipartite graphs with nullity n − 6. In this paper, we study similar problem for a class of tripartite graphs. As observed the nullity problem in tripartite graphs does not follow as an extension to that of the nullity of bipartite graphs, this makes the study of nullity in tripartite graphs interesting. In this direction, we obtain the nullity set of a class of n-vertex tripartite graphs and characterize these tripartite graphs with nullity n − 4. We also characterize some tripartite graphs with nullity n − 6 in this class.
3
Prasetyo, Joko. "FAKTORISASI PADA GRAF REGULER." EDUPEDIA 4, no. 1 (April 18, 2020): 75. http://dx.doi.org/10.24269/ed.v4i1.434.
Full textAbstract:
This research aims to: (1) know the criteria of a graph that has a -factor, (2) know the conditions of a regular graph that has a 1-factorization , (3) know the conditions of a regular graph that has a 2-factorization.This research is a qualitative descriptive study using the method of literature study or literature review where a study of books, scientific journals, and other literature languages is carried out relating to factorization on regular graphs. This research begins by discussing the definitions and examples of euler graphs and regular bipartite multigraphs. Next in reviewing the terms of a regular graph which has a 1-factorization and which has a 2-factorization, it starts by discussing the definition and theorem of matching on bipartite graphs, definitions and examples of factorization graphs, then discussing the proof of theorem of regular graphs that have a 1-factor and a regular graph which has a 2-factor.The results of this study indicate that: (1) Graph is said to be -factorable or can be factored into -factor , if can be decomposed or be eksplained into spanning subgraphs , where each has a -factor and is edge-disjoint from , that is 1) 2) … n) = . (2) The condition for a graph that has a 1-factorization is, if the graph is a -regular bipartite multigraph, with . (3) The condition for a graph that has a 2-factorization is, if the graph is a -regular graph, with . Key words: Bipartite graphs, Factorization, Decomposition, Regular graph.
4
A. Antony mary, A., A. Amutha, and M. S. Franklin Thamil Selvi. "A Study on Slope Number of Certain Classes of Bipartite Graphs." International Journal of Engineering & Technology 7, no. 4.10 (October 2, 2018): 440. http://dx.doi.org/10.14419/ijet.v7i4.10.21036.
Full textAbstract:
Graph drawing is the most important area of mathematics and computer science which combines methods from geometric graph theory and information visualization. Generally, graphs are represented to explore some intellectual ideas. Graph drawing is the familiar concept of graph theory. It has many quality measures and one among them is the slope number. Slope number problem is an optimization problem and is NP-hard to determine the slope number of any arbitrary graph. In the present paper, the investigation on slope number of bipartite graph is studied elaborately. Since the bipartite graphs creates one of the most intensively investigated classes of graphs, we consider few classes of graphs and discussed structural behavior of such graphs.
5
PANDA, SWARUP. "Inverses of bicyclic graphs." Electronic Journal of Linear Algebra 32 (February 6, 2017): 217–31. http://dx.doi.org/10.13001/1081-3810.3322.
Full textAbstract:
A graph G is said to be nonsingular (resp., singular) if its adjacency matrix A(G) is nonsingular (resp., singular). The inverse of a nonsingular graph G is the unique weighted graph whose adjacency matrix is similar to the inverse of the adjacency matrix A(G) via a diagonal matrix of ±1s. Consider connected bipartite graphs with unique perfect matchings such that the graph obtained by contracting all matching edges is also bipartite. In [C.D. Godsil. Inverses of trees. Combinatorica, 5(1):33â39, 1985.], Godsil proved that such graphs are invertible. He posed the question of characterizing the bipartite graphs with unique perfect matchings possessing inverses. In this article, Godsilâs question for the class of bicyclic graphs is answered.
6
FÜRER, MARTIN, and SHIVA PRASAD KASIVISWANATHAN. "Approximately Counting Embeddings into Random Graphs." Combinatorics, Probability and Computing 23, no. 6 (July 9, 2014): 1028–56. http://dx.doi.org/10.1017/s0963548314000339.
Full textAbstract:
LetHbe a graph, and letCH(G) be the number of (subgraph isomorphic) copies ofHcontained in a graphG. We investigate the fundamental problem of estimatingCH(G). Previous results cover only a few specific instances of this general problem, for example the case whenHhas degree at most one (the monomer-dimer problem). In this paper we present the first general subcase of the subgraph isomorphism counting problem, which is almost always efficiently approximable. The results rely on a new graph decomposition technique. Informally, the decomposition is a labelling of the vertices such that every edge is between vertices with different labels, and for every vertex all neighbours with a higher label have identical labels. The labelling implicitly generates a sequence of bipartite graphs, which permits us to break the problem of counting embeddings of large subgraphs into that of counting embeddings of small subgraphs. Using this method, we present a simple randomized algorithm for the counting problem. For all decomposable graphsHand all graphsG, the algorithm is an unbiased estimator. Furthermore, for all graphsHhaving a decomposition where each of the bipartite graphs generated is small and almost all graphsG, the algorithm is a fully polynomial randomized approximation scheme.We show that the graph classes ofHfor which we obtain a fully polynomial randomized approximation scheme for almost allGincludes graphs of degree at most two, bounded-degree forests, bounded-width grid graphs, subdivision of bounded-degree graphs, and major subclasses of outerplanar graphs, series-parallel graphs and planar graphs of large girth, whereas unbounded-width grid graphs are excluded. Moreover, our general technique can easily be applied to proving many more similar results.
7
Metsidik, Metrose. "Eulerian and Even-Face Graph Partial Duals." Symmetry 13, no. 8 (August 11, 2021): 1475. http://dx.doi.org/10.3390/sym13081475.
Full textAbstract:
Eulerian and bipartite graph is a dual symmetric concept in Graph theory. It is well-known that a plane graph is Eulerian if and only if its geometric dual is bipartite. In this paper, we generalize the well-known result to embedded graphs and partial duals of cellularly embedded graphs, and characterize Eulerian and even-face graph partial duals of a cellularly embedded graph by means of half-edge orientations of its medial graph.
8
FANKHAUSER, STEFAN, KASPAR RIESEN, HORST BUNKE, and PETER DICKINSON. "SUBOPTIMAL GRAPH ISOMORPHISM USING BIPARTITE MATCHING." International Journal of Pattern Recognition and Artificial Intelligence 26, no. 06 (September 2012): 1250013. http://dx.doi.org/10.1142/s0218001412500139.
Full textAbstract:
Graphs provide us with a flexible and powerful way to represent objects in various areas of computer science. One of the main drawbacks is, however, that many standard algorithms on graphs have a high computational complexity. The present paper considers the problem of graph isomorphism, i.e. checking two graphs for identity. A novel approach for the efficient computation of graph isomorphism is presented. The proposed algorithm is based on bipartite graph matching by means of an assignment algorithm. The algorithmic framework is suboptimal in the sense of possibly rejecting pairs of graphs without making a decision. As an advantage, however, it offers polynomial runtime. In experiments on diverse graph data sets we demonstrate substantial speedups of our proposed method over several standard procedures for graph isomorphism. Furthermore, although the computational framework for isomorphism is suboptimal, we show that the proposed algorithm rejects only very few pairs of graphs and otherwise returns correct results.
9
D'Souza, S., K. P. Girija, and H. J. Gowtham. "Цветовая энергия некоторых кластерных графов." Владикавказский математический журнал, no. 2 (June 24, 2021): 51–64. http://dx.doi.org/10.46698/x5522-9720-4842-z.
Full textAbstract:
Let $G$ be a simple connected graph. The energy of a graph $G$ is defined as sum of the absolute eigenvalues of an adjacency matrix of the graph $G$. It represents a proper generalization of a formula valid for the total $\pi$-electron energy of a conjugated hydrocarbon as calculated by the Huckel molecular orbital (HMO) method in quantum chemistry. A coloring of a graph $G$ is a coloring of its vertices such that no two adjacent vertices share the same color. The minimum number of colors needed for the coloring of a graph $G$ is called the chromatic number of $G$ and is denoted by $\chi(G)$. The color energy of a graph $G$ is defined as the sum of absolute values of the color eigenvalues of $G$. The graphs with large number of edges are referred as cluster graphs. Cluster graphs are graphs obtained from complete graphs by deleting few edges according to some criteria. It can be obtained on deleting some edges incident on a vertex, deletion of independent edges/triangles/cliques/path P3 etc. Bipartite cluster graphs are obtained by deleting few edges from complete bipartite graphs according to some rule. In this paper, the color energy of cluster graphs and bipartite cluster graphs are studied.
10
Basavanagoud, B., and Roopa S. Kusugal. "On the Line Degree Splitting Graph of a Graph." Bulletin of Mathematical Sciences and Applications 18 (May 2017): 1–10. http://dx.doi.org/10.18052/www.scipress.com/bmsa.18.1.
Full textAbstract:
In this paper, we introduce the concept of the line degree splitting graph of a graph. We obtain some properties of this graph. We find the girth of the line degree splitting graphs. Further, we establish the characterization of graphs whose line degree splitting graphs are eulerian, complete bipartite graphs and complete graphs.
Dissertations / Theses on the topic "Graphe biparti"
1
Topart, Hélène. "Etude d’une nouvelle classe de graphes : les graphes hypotriangulés." Thesis, Paris, CNAM, 2011. http://www.theses.fr/2011CNAM0776/document.
Full textAbstract:
Dans cette thèse, nous définissons une nouvelle classe de graphes : les graphes hypotriangulés. Les graphes hypotriangulés vérifient que pour tout chemin de longueur deux, il existe une arête ou un autre chemin de longueur deux entre ses extrémités. Cette classe permet par exemple de modéliser des réseaux robustes. En effet, nous montrons que dans de tels graphes, la suppression d'une arête ou d'un sommet ne modifie pas la distance initiale entre toutes paires de sommets non adjacents. Ensuite, nous étudions et démontrons plusieurs propriétés pour cette classe de graphes. En particulier, après avoir introduit une famille de partitions spécifiques, nous montrons les relations entre certains éléments de cette famille et leur caractère hypotriangulé. De plus, grâce à ces partitions, nous caractérisons les graphes hypotriangulés minimum, qui, parmi les graphes hypotriangulés connexes, minimisent le nombre d'arêtes pour un nombre de sommets fixés.Dans une deuxième partie, nous étudions la complexité, pour la classe des graphes hypotriangulés, de problèmes difficiles dans le cas général. Nous montrons d'abord que les problèmes classiques de cycle hamiltonien, coloration, clique maximum et stable maximum restent NP-difficiles pour cette classe de graphes. Ensuite, nous nous intéressons à des problèmes de modification de graphes, pour lesquels il s'agit de déterminer le nombre minimal d'arêtes à ajouter ou supprimer à un graphe pour obtenir un graphe hypotriangulé : nous montrons la complexité de ces problèmes pour plusieurs classes de graphesIn this thesis, we define a new class of graphs : the hypochordal graphs. These graphs satisfy that for any path of length two, there exists a chord or another path of length two between its two endpoints. This class can represent robust networks. Indeed, we show that in such graphs, in the case of an edge or a vertex deletion, the distance beween any pair of nonadjacent vertices remains unchanged. Then, we study several properties for this class of graphs. Especially, after introducing a family of specific partitions, we show the relations between some of these partitions and hypochordality. Moreover, thanks to these partitions, we characterise minimum hypochordal graph, that are, among connected hypochordal graphs, those that minimise the number of edges for a given number of vertices. In a second part, we study the complexity, for hypochordal graphs, of problems that are NP-hard in the general case. We first show that the classical problems of hamiltonian cycle, colouring, maximum clique and maximum stable set remain NP-hard for this class of graphs. Then, we analyse graph modification problems : deciding the minimal number of edges to add or delete from a graph, in order to obtain an hypochordal graph. We study the complexity of these problems for sevaral classes of graphs
2
Topart, Hélène. "Etude d'une nouvelle classe de graphes : les graphes hypotriangulés." Phd thesis, Conservatoire national des arts et metiers - CNAM, 2011. http://tel.archives-ouvertes.fr/tel-00686960.
Full textAbstract:
Dans cette thèse, nous définissons une nouvelle classe de graphes : les graphes hypotriangulés. Les graphes hypotriangulés vérifient que pour tout chemin de longueur deux, il existe une arête ou un autre chemin de longueur deux entre ses extrémités. Cette classe permet par exemple de modéliser des réseaux robustes. En effet, nous montrons que dans de tels graphes, la suppression d'une arête ou d'un sommet ne modifie pas la distance initiale entre toutes paires de sommets non adjacents. Ensuite, nous étudions et démontrons plusieurs propriétés pour cette classe de graphes. En particulier, après avoir introduit une famille de partitions spécifiques, nous montrons les relations entre certains éléments de cette famille et leur caractère hypotriangulé. De plus, grâce à ces partitions, nous caractérisons les graphes hypotriangulés minimum, qui, parmi les graphes hypotriangulés connexes, minimisent le nombre d'arêtes pour un nombre de sommets fixés.Dans une deuxième partie, nous étudions la complexité, pour la classe des graphes hypotriangulés, de problèmes difficiles dans le cas général. Nous montrons d'abord que les problèmes classiques de cycle hamiltonien, coloration, clique maximum et stable maximum restent NP-difficiles pour cette classe de graphes. Ensuite, nous nous intéressons à des problèmes de modification de graphes, pour lesquels il s'agit de déterminer le nombre minimal d'arêtes à ajouter ou supprimer à un graphe pour obtenir un graphe hypotriangulé : nous montrons la complexité de ces problèmes pour plusieurs classes de graphes.
3
Barkaoui, Kamel. "Contribution aux methodes d'analyse des reseaux de petri par la theorie des graphes." Paris 6, 1988. http://www.theses.fr/1988PA066041.
Full textAbstract:
On introduit la notion de composante preconservative minimale (theoreme). On fournit une nouvelle caracterisation de la minimalite des verrous et des trappes. On etablit un lemme permettant d'etendre le domaine de validite de la propriete communer (condition suffisante de vivacite)
4
Cotté, Grégoire. "d-extensibles, d-bloqueurs et d-transversaux de problèmes d'optimisation combinatoire." Thesis, Paris, CNAM, 2016. http://www.theses.fr/2016CNAM1037/document.
Full textAbstract:
Dans cette thèse, nous étudions trois catégories de problèmes : les d-extensibles, les d-bloqueurs et les d-transversaux.Les d-extensibles de stables optimaux sont des ensembles de sommets d'un graphe G tels que tout stable de cardinal d du sous-graphe induit par un d-extensible peut être étendu à un stable optimal de G à l'aide de sommets qui n'appartiennent pas au d-extensible. Nous étudions les d-extensibles de cardinal maximal de stables dans les graphes bipartis. Nous démontrons quelques propriétés structurelles puis nous déterminons une borne inférieure du cardinal maximal d'un d-extensible. Nous étudions quelques classes de graphes dans lesquelles déterminer un d-extensible optimal de stables est un problème polynomial. Nous nous intéressons ensuite aux d-extensibles de stables dans les arbres. Nous prouvons plusieurs propriétés structurelles, déterminons une autre borne inférieure du cardinal maximal d'un d-extensible et étudions quelques classes d'arbres dans lesquelles déterminer un d-extensible optimal de stables est un problème polynomial.Les d-bloqueurs de stables sont des ensembles de sommets d'un graphe G tels que, si on retire les sommets d'un d-bloqueur, le cardinal maximal d'un stable du graphe induit par les sommets restants est inférieur d'au moins d au cardinal maximal d'un stable du graphe initial. Nous nous intéressons ici aux d-bloqueurs de coût minimal de stables dans les arbres. Après avoir prouvé une caractérisation des d-bloqueurs de stables dans les arbres, nous démontrons que déterminer un d-bloqueur de coût minimal de stable est un problème polynomial dans une classe d'arbres particulière.Soit Pi un problème d'optimisation sur un ensemble d'éléments fini. Un d-transversal de Pi est un ensembles d'éléments tel que l'intersection entre le d-transversal et toute solution optimale au problème Pi est de cardinal supérieur égal à d. Nous proposons ici une approche de génération de contraintes pour déterminer des d-transversaux de cardinal maximal de problèmes modélisés par des programmes mathématiques en variables binaires. Nous étudions deux variantes de cette approche que nous testons sur des instances de graphes générés aléatoirement pour déterminer des d-transversaux de stables optimaux et des d-transversaux de couplages optimauxIn this thesis, we study three types of problems : the d-extensibles sets, the d-blockers and the d-transversals.In a graph G, a d-extensible set of maximum independent sets is a subset of vertices of G such that every stable set of cardinality d in the subgraph restricted to the d-extensible set can be extented to a maximum stable set of G using only vertices that do not belong to the d-extensible set. We study d-extensible sets of mxaimum cardinality of stable sets in bipartite graphs. We show some structural properties and we determine a lower bound of the maximum cardinality of a d-extensible set. We consider some classes of graph where finding an optimum d-extensible set can be done in polynomial time. Then, we study the d-extensibles sets of stable sets in trees. We prove some properties on the structures of the d-extensibles sets and we determine another lower bound of the maximum cardinality of a d-extensible set. Finaly, we study somme classes of tree where a d-extensible sets of maximum cardinality can be done in polynomial time.In a graph G, a d-blocker is a subset of vertices such that, if removed, a maximum stable set of the resulting subgraph is of cardinality at most the cardinality of a maximum stable set of G minus d. We study d-blocker of minimal cost of stable sets in tree.We prove a caracterisation of d-blockers in tree and we study a particular classe of trees where computing a d-blocker of minimal cost of stable sets can be done in polynomial time.Let Pi be an optimisation problem on a finite set of elements. A d-transversal of Pi is a subset of elements such that the intersection between the d-transversal and every optimal solution of Pi contains at lest d elements. We propose an approach to compute d-transversal of any optimisation problem modelised by mathematical program with binary variables. We use a contraints generation approach. We compare two variations of this approach on randomly generated graph by computing d-transversals of stables sets and d-transversals of matching
5
Viana, do Espírito Santo Ilísio. "Inspection automatisée d’assemblages mécaniques aéronautiques par vision artificielle : une approche exploitant le modèle CAO." Thesis, Ecole nationale des Mines d'Albi-Carmaux, 2016. http://www.theses.fr/2016EMAC0022/document.
Full textAbstract:
Les travaux présentés dans ce manuscrit s’inscrivent dans le contexte de l’inspection automatisée d’assemblages mécaniques aéronautiques par vision artificielle. Il s’agit de décider si l’assemblage mécanique a été correctement réalisé (assemblage conforme). Les travaux ont été menés dans le cadre de deux projets industriels. Le projet CAAMVis d’une part, dans lequel le capteur d’inspection est constitué d’une double tête stéréoscopique portée par un robot, le projet Lynx© d’autre part, dans lequel le capteur d’inspection est une caméra Pan/Tilt/Zoom (vision monoculaire). Ces deux projets ont pour point commun la volonté d’exploiter au mieux le modèle CAO de l’assemblage (qui fournit l’état de référence souhaité) dans la tâche d’inspection qui est basée sur l’analyse de l’image ou des images 2D fournies par le capteur. La méthode développée consiste à comparer une image 2D acquise par le capteur (désignée par « image réelle ») avec une image 2D synthétique, générée à partir du modèle CAO. Les images réelles et synthétiques sont segmentées puis décomposées en un ensemble de primitives 2D. Ces primitives sont ensuite appariées, en exploitant des concepts de la théorie de graphes, notamment l’utilisation d’un graphe biparti pour s’assurer du respect de la contrainte d’unicité dans le processus d’appariement. Le résultat de l’appariement permet de statuer sur la conformité ou la non-conformité de l’assemblage. L’approche proposée a été validée à la fois sur des données de simulation et sur des données réelles acquises dans le cadre des projets sus-citésThe work presented in this manuscript deals with automated inspection of aeronautical mechanical parts using computer vision. The goal is to decide whether a mechanical assembly has been assembled correctly i.e. if it is compliant with the specifications. This work was conducted within two industrial projects. On one hand the CAAMVis project, in which the inspection sensor consists of a dual stereoscopic head (stereovision) carried by a robot, on the other hand the Lynx© project, in which the inspection sensor is a single Pan/Tilt/Zoom camera (monocular vision). These two projects share the common objective of exploiting as much as possible the CAD model of the assembly (which provides the desired reference state) in the inspection task which is based on the analysis of the 2D images provided by the sensor. The proposed method consists in comparing a 2D image acquired by the sensor (referred to as "real image") with a synthetic 2D image generated from the CAD model. The real and synthetic images are segmented and then decomposed into a set of 2D primitives. These primitives are then matched by exploiting concepts from the graph theory, namely the use of a bipartite graph to guarantee the respect of the uniqueness constraint required in such a matching process. The matching result allows to decide whether the assembly has been assembled correctly or not. The proposed approach was validated on both simulation data and real data acquired within the above-mentioned projects
6
Tackx, Raphaël. "Analyse de la structure communautaire des réseaux bipartis." Electronic Thesis or Diss., Sorbonne université, 2018. https://accesdistant.sorbonne-universite.fr/login?url=https://theses-intra.sorbonne-universite.fr/2018SORUS550.pdf.
Full textAbstract:
Il existe dans le monde réel un nombre important de réseaux qui apparaissent naturellement, on les retrouve un peu partout, dans de nombreuses disciplines, par exemple en informatique avec les réseaux de routeurs, les réseaux de satellites, les réseaux de pages Web, en biologie avec les réseaux des neurones, en écologie avec les réseaux d’interactions biologiques, en linguistiques avec les réseaux de synonymes, en droit avec les réseaux de décisions juridiques, en économie avec les réseaux interbancaires, en sciences humaines avec les réseaux sociaux. De manière générale, un réseau reflète les interactions entre les nombreuses entités d’un système. Ces interactions peuvent être de différentes natures, un lien social ou un lien d’amitié dans un réseau social constitué de personnes, un câble dans un réseau de routeurs, une réaction chimique dans un réseau biologique de protéines, un hyperlien dans un réseau de pages Web, etc. Plus encore, la rapide démocratisation du numérique dans nos sociétés, avec Internet notamment, a pour conséquence de produire de nouveaux systèmes qui peuvent être représentés sous forme de réseaux. Finalement, tous ces réseaux présentent des particularités bien spécifiques : ils sont issus de contextes pratiques, ils sont le plus souvent de grande taille (on retrouve quelques fois des réseaux constitués de plusieurs milliards de nœuds et de liens, contenant donc une grande quantité d’information), ils présentent des propriétés statistiques communes. À cet égard, ils sont regroupés sous l’appellation de réseaux réels, graphes de terrain ou encore réseaux complexes. Aujourd'hui, la science des réseaux est un domaine de recherche à part entière dont l’enjeu principal est de parvenir à décrire et modéliser ces réseaux avec précision afin de révéler leurs caractéristiques générales et de mieux comprendre leurs mécanismes. La plupart des travaux dans ce domaine utilisent le formalisme des graphes qui fournit un ensemble d’outils mathématiques particulièrement adaptés à l’analyse topologique et structurelle des réseaux. Il existe de nombreuses applications dans ce domaine, par exemple des applications concernant la propagation d’épidémie ou de virus informatique, la fragilité du réseau en cas de panne, sa résilience en cas d’attaque, l’étude de la dynamique pour prédire l’apparition de nouveaux liens, la recommandation, etc. L’un des problèmes complexes actuels, qui a beaucoup d’applications, est l’identification de la structure communautaire. La grande majorité des réseaux réels sont caractérisés par des niveaux d’organisation dans leur structure mésoscopique. Du fait de la faible densité globale des réseaux réels couplée à la forte densité locale, on observe la présence de groupes de nœuds fortement liés entre eux et plus faiblement liés avec le reste du réseau, que l’on appelle communautés. Ces structures ont également du sens dans le réseau lui-même, par exemple les communautés d’un réseau social peuvent correspondre à des groupes sociaux (amis, familles, etc.), les communautés d’un réseau de protéines peuvent traduire des réponses fonctionnelles, elles peuvent correspondre à des sujets similaires dans un réseau de pages Web, pour donner quelques exemples [...]In the real world, numerous networks appear naturally, they are everywhere, in many disciplines, for example in computer science with router networks, satellite networks, webpage networks, in biology with neural networks, in ecology with biological interaction networks, in linguistic with synonym networks, in law with legal decision networks, in economy with interbank networks, in social sciences and humanities with social networks. Generally, a network reflects the interactions between many entities of a system. These interactions have different sources, a social link or a friendship link in a social network, a cable in a router network, a chemical reaction in a protein-protein interaction network, a hyperlink in a webpage network. Furthermore, the rapid democratization of digital technology in our societies, with internet in particular, leads to create new systems which can be seen as networks. Finally, all these networks depict very specific features : they come from pratical contexts, most of the time they are big (they may be comprised of several billion of nodes and links, containing a large amount of information), they share statistical properties. In this regard, they are called real-world networks or complex networks. Nowaday, network science is a research area in its own right focusing on describing and modeling these networks in order to reveal their main features and improve our understanding of their mecanisms. Most of the works in this area use graphs formalism which provides a set of mathematical tools well suited for analyzing the topology of these networks. It exists many applications, for instance applications in spread of epidemy or computer viruses, weakness of networks in case of a breakdown, attack resilience, study for link prediction, recommandation, etc. One of the major issue is the identification of community structure. The large majority of real-world networks depicts several levels of organization in their structure. Because of there is a weak global density coupled with a strong local density, we observe that nodes are usually organized into groups, called communities, which are more internally connected than they are to the rest of the network. Moreover, these structures have a meaning in the network itself, for example communities of a social network may correspond to social groups (friends, families, etc.), communities of a protein-protein network may translate fonctions of a cell, communities may be also related to similar subjects in a webpage network [...]
7
Al-Iedani, Najat Hameed Qasim. "Contribution à la résolution des problèmes d'optimisation combinatoire : cas du problème des k-clusters dans un graphe biparti et du problème de sac à dos quadratique." Thesis, Amiens, 2017. http://www.theses.fr/2017AMIE0035/document.
Full textAbstract:
Les problèmes d'optimisation combinatoire sont d'un grand intérêt à la fois pour le monde scientifique et le monde industriel. Les enjeux scientifiques, économiques, environnementaux et sociaux sont très nombreux et très importants. C'est pour cela que la communauté scientifique mondiale recherche depuis longtemps des méthodes de modélisation, de simplification et de résolution de ces problèmes. Parmi les problèmes combinatoires les plus connus se trouvent les problèmes de sac à dos et les problèmes liés aux décompositions des graphes. Nous nous sommes intéressés dans cette thèse à deux problèmes importants : - Le problème de regroupement dans un graphe biparti ; - Le problème de sac à dos quadratique. Le problème de regroupement dans un graphe biparti a de nombreuses applications dans le domaine des télécommunications. Il a également un grand intérêt théorique dans la modélisation, la décomposition et la résolution de plusieurs autres problèmes combinatoires. Le problème de sac à dos quadratique a un large champ d'applications théoriques et pratiques dans nombreux domaines. Il est très utile dans la modélisation et la résolution dans un contexte de gestion des exclusions par exemple. Ces deux problèmes sont hautement combinatoires et sont très difficiles à résoudre d'une manière optimale d'un point de vue informatique. La résolution de ce type de problèmes peut se faire de deux manières : - La résolution optimale, dite également exacte, qui s’appuie sur des modélisations et des méthodes mathématiques puissantes dont l'objectif est d'identifier une solution optimale du problème traité. - La résolution approchée, qui s'appuie principalement sur des algorithmes capables d'approcher la solution optimale du problème traité mais sans garantir l'optimalité du résultat. Les méthodes approchées sont les plus utilisées par les informaticiens dans la résolution des problèmes issus de l'industrie et des services car ces méthodes permettent de résoudre des problèmes de grande taille et de répondre aux exigences fonctionnelles des donneurs d'ordres. Il existe aussi des méthodes de résolution hydrides qui peuvent combiner plusieurs méthodes de résolution approchées ou exactes et qui utilisent généralement des techniques de décomposition du problème initial pour permettre l'hybridation. C'est dans ce sens que s'oriente cette thèse. Nous proposons dans cette thèse deux méthodes de résolution hydriques : - Une première méthode hydride pour le problème de regroupement dans un graphe biparti qui combine une recherche par voisinage et un algorithme approché complémentaire. - Une deuxième méthode hybride pour le problème du sac à dos quadratique qui combine une recherche par voisinage et une méthode de réduction/fix-ation des variablesSince long time, the scientific world has sought for modeling, simplification and resolution of combinatorial optimization problems, because of these problems are most interest for the scientific and the industrial world and for the fields of operational research and computer science. The objective of this thesis is to solve the difficult combinatorial optimization problems using approximate resolution methods. And, we were interested on two important problems that find several significant applications in real world. The first part of the thesis is devoted to the K-clusters in a bipartite graph that has been applied in the field of telecommunication. The second part of the thesis addresses to the quadratic knapsack problem that can be used to accommodate a wide range of practical applications in numerous fields. On the other hand, these problems are highly combinatorial and difficult to solve from computational perspective. The K-clustering minimum bi-clique completion problem (K - CmBCP) was presented in the latest date and it is very significant in real world and it has been applied to several real applications such as aggregation of multicast sessions. Since telecommunication network cannot manage many multicast sessions at the same time, it is hence necessary to group the sessions into a limited number of clusters. We note that, the hybrid resolution methods can combine several approximate resolution methods or optimal resolution and approximate resolution and which generally use decomposition techniques of the initial problem to allow hybridation. In this thesis, we propose two hybrid resolution methods: A first hybrid method for the problem of K-clusters in a bipartite graph that combines a neighborhood search and a complementary algorithm. A second hybrid method for the quadratic knapsack problem which combines a large neighborhood search with a variable reduction / fixing method. The proposed algorithm is capable of solving the small, large and very large size instances of the QKP that cannot be solved by Cplex solver or by other methods
8
Thiant, Nicolas. "Constructions et reconstructions de pavages de dominos." Paris 6, 2006. http://www.theses.fr/2006PA066418.
Full textAbstract:
Cette thèse est une contribution à l'étude de problèmes de pavages par des dominos. Nous montrons comment élargir au cas d'un polyomino avec des trous la méthode de Thurston qui permet de paver en temps linéaire un polyomino sans trous par des dominos. Nous présentons un algorithme de pavage de complexité O(kn) pour un polyomino avec n cellules et k trous. En particulier, cet algorithme est linéaire pour un polyomino avec un nombre borné de trous. Nous exposons aussi l'état de nos recherches sur le problème du pavage de cardinalité maximale et, plus généralement, sur celui du couplage maximum dans un graphe biparti plan. Nous présentons un algorithme original de couplage dont la complexité reste encore à déterminer. Nous considérons enfin le problème de la reconstruction du pavage d'un rectangle à partir de ses projections orthogonales. Ce problème connu depuis une dizaine d'années restait non résolu. Nous présentons un algorithme polynomial qui réalise cette reconstruction.
9
Aïder, Méziane. "Réseaux d'interconnexion bipartis : colorations généralisées dans les graphes." Phd thesis, Grenoble 1, 1987. http://tel.archives-ouvertes.fr/tel-00325779.
Full textAbstract:
Étude sur les graphes bipartis orientes de Moore montrant que de tels graphes existent, pour certaines valeurs du diamètre, et servent a la construction d'une classe de graphes bipartis orientes, asymptotiquement optimaux. Dans la deuxième partie du travail, quelques notions de coloration des graphes sont présentées. Celles-ci permettent de généraliser certains résultats déjà connus dans le cadre de la coloration habituelle et d'en obtenir d'autres plutôt spécifiques a ces notions. La généralisation de la notion de perfection en b-perfection est proposée ce qui permet l'obtention des graphes triangules représentant la seule classe de graphes b-parfaits
10
Ross, Christopher Jon. "Properties of Random Threshold and Bipartite Graphs." The Ohio State University, 2011. http://rave.ohiolink.edu/etdc/view?acc_num=osu1306296991.
Full textBooks on the topic "Graphe biparti"
1
Asratian, Armen S. Bipartite graphs and their applications. Cambridge, U.K: Cambridge University Press, 1998.
Find full text
2
Justesen, Jørn. Two-dimensional information theory and coding: With application to graphics and high-density storage media. Cambridge: Cambridge University Press, 2010.
Find full text
3
Justesen, Jørn. Two-dimensional information theory and coding: With application to graphics and high-density storage media. Cambridge, UK: Cambridge University Press, 2010.
Find full text
4
Søren, Forchhammer, ed. Two-dimensional information theory and coding: With application to graphics and high-density storage media. Cambridge, UK: Cambridge University Press, 2010.
Find full text
5
Justesen, Jørn. Two-dimensional information theory and coding: With application to graphics and high-density storage media. Cambridge, UK: Cambridge University Press, 2010.
Find full text
8
Coolen, A. C. C., A. Annibale, and E. S. Roberts. Applications of random graphs. Oxford University Press, 2017. http://dx.doi.org/10.1093/oso/9780198709893.003.0011.
Full textAbstract:
This chapter reviews graph generation techniques in the context of applications. The first case study is power grids, where proposed strategies to prevent blackouts have been tested on tailored random graphs. The second case study is in social networks. Applications of random graphs to social networks are extremely wide ranging – the particular aspect looked at here is modelling the spread of disease on a social network – and how a particular construction based on projecting from a bipartite graph successfully captures some of the clustering observed in real social networks. The third case study is on null models of food webs, discussing the specific constraints relevant to this application, and the topological features which may contribute to the stability of an ecosystem. The final case study is taken from molecular biology, discussing the importance of unbiased graph sampling when considering if motifs are over-represented in a protein–protein interaction network.
9
Newman, Mark. Mathematics of networks. Oxford University Press, 2018. http://dx.doi.org/10.1093/oso/9780198805090.003.0006.
Full textAbstract:
An introduction to the mathematical tools used in the study of networks. Topics discussed include: the adjacency matrix; weighted, directed, acyclic, and bipartite networks; multilayer and dynamic networks; trees; planar networks. Some basic properties of networks are then discussed, including degrees, density and sparsity, paths on networks, component structure, and connectivity and cut sets. The final part of the chapter focuses on the graph Laplacian and its applications to network visualization, graph partitioning, the theory of random walks, and other problems.
10
Newman, Mark. The configuration model. Oxford University Press, 2018. http://dx.doi.org/10.1093/oso/9780198805090.003.0012.
Full textAbstract:
A discussion of the most fundamental of network models, the configuration model, which is a random graph model of a network with a specified degree sequence. Following a definition of the model a number of basic properties are derived, including the probability of an edge, the expected number of multiedges, the excess degree distribution, the friendship paradox, and the clustering coefficient. This is followed by derivations of some more advanced properties including the condition for the existence of a giant component, the size of the giant component, the average size of a small component, and the expected diameter. Generating function methods for network models are also introduced and used to perform some more advanced calculations, such as the calculation of the distribution of the number of second neighbors of a node and the complete distribution of sizes of small components. The chapter ends with a brief discussion of extensions of the configuration model to directed networks, bipartite networks, networks with degree correlations, networks with high clustering, and networks with community structure, among other possibilities.
Book chapters on the topic "Graphe biparti"
1
Ovchinnikov, Sergei. "Bipartite Graphs." In Universitext, 23–49. New York, NY: Springer New York, 2011. http://dx.doi.org/10.1007/978-1-4614-0797-3_2.
Full text
2
Nitzsche, Manfred. "Bipartite Graphen." In Graphen für Einsteiger, 101–21. Wiesbaden: Vieweg+Teubner Verlag, 2004. http://dx.doi.org/10.1007/978-3-322-92879-5_6.
Full text
3
Simon, Klaus. "Bipartite Graphen." In Effiziente Algorithmen für perfekte Graphen, 97–147. Wiesbaden: Vieweg+Teubner Verlag, 1992. http://dx.doi.org/10.1007/978-3-322-94768-0_5.
Full text
4
Nitzsche, Manfred. "Bipartite Graphen." In Graphen für Einsteiger, 101–21. Wiesbaden: Vieweg+Teubner Verlag, 2005. http://dx.doi.org/10.1007/978-3-322-92380-6_6.
Full text
5
Nitzsche, Manfred. "Bipartite Graphen." In Graphen für Einsteiger, 109–31. Wiesbaden: Vieweg+Teubner, 2009. http://dx.doi.org/10.1007/978-3-8348-9968-2_6.
Full text
6
Zepeda-Mendoza, Marie Lisandra, and Osbaldo Resendis-Antonio. "Bipartite Graph." In Encyclopedia of Systems Biology, 147–48. New York, NY: Springer New York, 2013. http://dx.doi.org/10.1007/978-1-4419-9863-7_1370.
Full text
7
Chalopin, Jérémie, and Daniël Paulusma. "Packing Bipartite Graphs with Covers of Complete Bipartite Graphs." In Lecture Notes in Computer Science, 276–87. Berlin, Heidelberg: Springer Berlin Heidelberg, 2010. http://dx.doi.org/10.1007/978-3-642-13073-1_25.
Full text
8
Di Giacomo, Emilio, Luca Grilli, and Giuseppe Liotta. "Drawing Bipartite Graphs on Two Curves." In Graph Drawing, 380–85. Berlin, Heidelberg: Springer Berlin Heidelberg, 2007. http://dx.doi.org/10.1007/978-3-540-70904-6_36.
Full text
9
Dean, Alice M., and Joan P. Hutchinson. "Rectangle-visibility representations of bipartite graphs." In Graph Drawing, 159–66. Berlin, Heidelberg: Springer Berlin Heidelberg, 1995. http://dx.doi.org/10.1007/3-540-58950-3_367.
Full text
10
Tanasescu, Cerasela, Ruxandra Marinescu-Ghemeci, and Alain Bretto. "Incidence Graphs of Bipartite G-Graphs." In Optimization Theory, Decision Making, and Operations Research Applications, 141–51. New York, NY: Springer New York, 2012. http://dx.doi.org/10.1007/978-1-4614-5134-1_9.
Full textConference papers on the topic "Graphe biparti"
1
Sobral, Gabriel A. G., Marina Groshaus, and André L. P. Guedes. "Biclique edge-choosability in some classes of graphs∗." In II Encontro de Teoria da Computação. Sociedade Brasileira de Computação - SBC, 2017. http://dx.doi.org/10.5753/etc.2017.3203.
Full textAbstract:
In this paper we study the problem of coloring the edges of a graph for any k-list assignment such that there is no maximal monochromatic biclique, in other words, the k-biclique edge-choosability problem. We prove that the K3free graphs that are not odd cycles are 2-star edge-choosable, chordal bipartite graphs are 2-biclique edge-choosable and we present a lower bound for the biclique choice index of power of cycles and power of paths. We also provide polynomial algorithms to compute a 2-biclique (star) edge-coloring for K3-free and chordal bipartite graphs for any given 2-list assignment to edges.
2
Shah, Meet, Ibrahim Zeid, and Sagar Kamarthi. "Bipartite Graphical Integration of Dielectrophoresis Process Models for Assembly of Carbon Nanotubes." In ASME 2009 International Mechanical Engineering Congress and Exposition. ASMEDC, 2009. http://dx.doi.org/10.1115/imece2009-11977.
Full textAbstract:
Dielectrophoresis is the process where nonuniform electric field causes the translational motion of uncharged, polarized particles. Recently dielectrophoresis has become the most widely used process in the field of nanomanufacturing as the translational motion of a carbon nanotube caused by the dielectrophoresis assembles it in the spacing between the electrodes. This process enables engineers to replace the traditional metal (copper or aluminum) wire with carbon nanotubes (CNTs) in the miniature electronic devices. Various process models have been developed and parametric studies have been carried out to understand the process better and to improve the quality and reliability of assembly of CNTs. We consolidate the scattered knowledge of the dielectrophoresis process and represent the integrated knowledge in the form of a complex network by connecting the process parameters based on the relationships they shares. We find that the bipartite relationships exist between some of the process parameters and we represent them in the form of bipartite graphs. We also represent these graphs as incidence matrices and verify whether each graph fulfills the condition of being bipartite. We apply the shortest path algorithm to find an even length path between the any two process parameters which turns out to be an efficient method to estimate the unknown state variables of the process and to access the real time state of the assembly process quickly and efficiently. One can also use bipartite graph to identify the non-contributing variables and eliminate the over constraint situation by applying Gauss elimination method.
3
Patel, Apurva, Patrick Andrews, and Joshua D. Summers. "Evaluating the Use of Artificial Neural Networks, Graph Theory, and Complexity Theory to Predict Automotive Assembly Defects." In ASME 2016 International Design Engineering Technical Conferences and Computers and Information in Engineering Conference. American Society of Mechanical Engineers, 2016. http://dx.doi.org/10.1115/detc2016-59664.
Full textAbstract:
Artificial Neural Networks (ANNs) have been used to predict assembly time and market value from assembly models. This was done by converting the assembly models into bipartite graphs and extracting 29 graph complexity metrics which were used to train the ANN prediction models. This paper presents the use of sub-assembly models instead of the entire assembly model to predict assembly quality defects at an automotive OEM. The size of the training set, order of the bipartite graph, selection of training set, and defect type were experimentally studied. With a training size of 28 parts, an interpolation focused training set selection, and second order graph seeding, over 70% of the predictions were within 100% of the target value. The study shows that with an increase in training size and careful selection of training sets, assembly defects can be predicted reliably from sub-assemblies complexity data.
4
Li, Chong, Kunyang Jia, Dan Shen, C. J. Richard Shi, and Hongxia Yang. "Hierarchical Representation Learning for Bipartite Graphs." In Twenty-Eighth International Joint Conference on Artificial Intelligence {IJCAI-19}. California: International Joint Conferences on Artificial Intelligence Organization, 2019. http://dx.doi.org/10.24963/ijcai.2019/398.
Full textAbstract:
Recommender systems on E-Commerce platforms track users' online behaviors and recommend relevant items according to each user’s interests and needs. Bipartite graphs that capture both user/item feature and use-item interactions have been demonstrated to be highly effective for this purpose. Recently, graph neural network (GNN) has been successfully applied in representation of bipartite graphs in industrial recommender systems. Providing individualized recommendation on a dynamic platform with billions of users is extremely challenging. A key observation is that the users of an online E-Commerce platform can be naturally clustered into a set of communities. We propose to cluster the users into a set of communities and make recommendations based on the information of the users in the community collectively. More specifically, embeddings are assigned to the communities and the user embedding is decomposed into two parts, each of which captures the community-level generalizations and individualized preferences respectively. The community embedding can be considered as an enhancement to the GNN methods that are inherently flat and do not learn hierarchical representations of graphs. The performance of the proposed algorithm is demonstrated on a public dataset and a world-leading E-Commerce company dataset.
5
Yan, Xinyu, Lijun Zhang, and Wu-Jun Li. "Semi-Supervised Deep Hashing with a Bipartite Graph." In Twenty-Sixth International Joint Conference on Artificial Intelligence. California: International Joint Conferences on Artificial Intelligence Organization, 2017. http://dx.doi.org/10.24963/ijcai.2017/452.
Full textAbstract:
Recently, deep learning has been successfully applied to the problem of hashing, yielding remarkable performance compared to traditional methods with hand-crafted features. However, most of existing deep hashing methods are designed for the supervised scenario and require a large number of labeled data. In this paper, we propose a novel semi-supervised hashing method for image retrieval, named Deep Hashing with a Bipartite Graph (DHBG), to simultaneously learn embeddings, features and hash codes. More specifically, we construct a bipartite graph to discover the underlying structure of data, based on which an embedding is generated for each instance. Then, we feed raw pixels as well as embeddings to a deep neural network, and concatenate the resulting features to determine the hash code. Compared to existing methods, DHBG is a universal framework that is able to utilize various types of graphs and losses. Furthermore, we propose an inductive variant of DHBG to support out-of-sample extensions. Experimental results on real datasets show that our DHBG outperforms state-of-the-art hashing methods.
6
Mathieson, James L., and Joshua D. Summers. "Complexity Metrics for Directional Node-Link System Representations: Theory and Applications." In ASME 2010 International Design Engineering Technical Conferences and Computers and Information in Engineering Conference. ASMEDC, 2010. http://dx.doi.org/10.1115/detc2010-28561.
Full textAbstract:
This paper presents an approach to defining and quantifying the complexity of systems as represented in mixed (directed and non-directed) bipartite graphs through the presentation of a central example as well as other applications. The approach presented defines nine measurements of different properties of the graph system. These measurements are derived from the representation of the system into a three dimension relational design structure matrix as well as the projections and transformations of this matrix. The metrics generated address dimensional and connective size, shortest path properties, and the decomposability of the system. Finally, a normalization and aggregate approach of these metrics is then given. This aggregation is visualized with spider graphs that facilitate viewing multiple aspects of complexity within a single perspective.
7
Weffort-Santos, Celso A., Christiane N. Campos, and Rafael C. S. Schouery. "Proper gap-labellings: on the edge and vertex variants." In XXXII Concurso de Teses e Dissertações da SBC. Sociedade Brasileira de Computação - SBC, 2019. http://dx.doi.org/10.5753/ctd.2019.6343.
Full textAbstract:
Given a simple graph G, an ordered pair (π, cπ) is said to be a gap- [k]-edge-labelling (resp. gap-[k]-vertex-labelling) ofG ifπ is an edge-labelling (vertex-labelling) on the set {1, . . . , k}, and cπ is a proper vertex-colouring such that every vertex of degree at least two has its colour induced by the largest difference among the labels of its incident edges (neighbours). The decision problems associated with these labellings are NP-complete for k ≥ 3, and even when k = 2 for some classes of graphs. This thesis presents a study of the computational complexity of these problems, structural properties for certain families of graphs and several labelling algorithms and techniques. First, we present an NP-completeness result for the family of subcubic bipartite graphs. Second, we present polynomial-time algorithms for families ofgraphs. Third, we introduce a new parameter associated with gap-[k]-vertex-labellings ofgraphs.
8
Moreira, Edré, Guilherme Oliveira Campos, and Wagner Meira Jr. "Dense Hierarchy Decomposition for Bipartite Graphs." In VII Symposium on Knowledge Discovery, Mining and Learning. Sociedade Brasileira de Computação - SBC, 2019. http://dx.doi.org/10.5753/kdmile.2019.8795.
Full textAbstract:
Dense subgraphs detection is a well known problem in Computer Science. Hierarchical organization of graphs as dense subgraphs, however, goes beyond simple clustering as it allows the analysis of the network at different scales. Despite the fact there are several works on hierarchical decomposition for unipartite graphs, only a few works for the bipartite case have been proposed. In this work we explore the problem of hierarchical decomposition of bipartite graphs. We propose an algorithm which we call weighted linking that produces denser and more compact hierarchies. The proposed algorithm is evaluated experimentally using several datasets and provided gains on most of them.
9
Caragiannis, Ioannis, and Evanthia Tsitsoka. "Deanonymizing Social Networks Using Structural Information." In Twenty-Eighth International Joint Conference on Artificial Intelligence {IJCAI-19}. California: International Joint Conferences on Artificial Intelligence Organization, 2019. http://dx.doi.org/10.24963/ijcai.2019/169.
Full textAbstract:
We study the following fundamental graph problem that models the important task of deanonymizing social networks. We are given a graph representing an eponymous social network and another graph, representing an anonymous social network, which has been produced by the original one after removing some of its nodes and adding some noise on the links. Our objective is to correctly associate as many nodes of the anonymous network as possible to their corresponding node in the eponymous network. We present two algorithms that attack the problem by exploiting only the structure of the two graphs. The first one exploits bipartite matching computations and is relatively fast. The second one is a local search heuristic which can use the outcome of our first algorithm as an initial solution and further improve it. We have applied our algorithms on inputs that have been produced by well-known random models for the generation of social networks as well as on inputs that use real social networks. Our algorithms can tolerate noise at the level of up to 10%. Interestingly, our results provide further evidence to which graph generation models are most suitable for modeling social networks and distinguish them from unrealistic ones.
10
Zhou, Peng, Liang Du, and Xuejun Li. "Self-paced Consensus Clustering with Bipartite Graph." In Twenty-Ninth International Joint Conference on Artificial Intelligence and Seventeenth Pacific Rim International Conference on Artificial Intelligence {IJCAI-PRICAI-20}. California: International Joint Conferences on Artificial Intelligence Organization, 2020. http://dx.doi.org/10.24963/ijcai.2020/295.
Full textAbstract:
Consensus clustering provides a framework to ensemble multiple clustering results to obtain a consensus and robust result. Most existing consensus clustering methods usually apply all data to ensemble learning, whereas ignoring the side effects caused by some difficult or unreliable instances. To tackle this problem, we propose a novel self-paced consensus clustering method to gradually involve instances from more reliable to less reliable ones into the ensemble learning. We first construct an initial bipartite graph from the multiple base clustering results, where the nodes represent the instances and clusters and the edges indicate that an instance belongs to a cluster. Then, we learn a structured bipartite graph from the initial one by self-paced learning, i.e., we automatically decide the reliability of each edge and involves the edges into graph learning in order of their reliability. At last, we obtain the final consensus clustering result from the learned bipartite graph. The extensive experimental results demonstrate the effectiveness and superiority of the proposed method.
Reports on the topic "Graphe biparti"
1
Zha, Hongyuan, Xiaofeng He, Chris Ding, Ming Gu, and Horst D. Simon. Bipartite graph partitioning and data clustering. Office of Scientific and Technical Information (OSTI), May 2001. http://dx.doi.org/10.2172/816202.
Full text
2
Kolda, Tamara G., Ali Pinar, and Sinan Aksoy. Measuring and Modeling Bipartite Graphs with Community Structure. Office of Scientific and Technical Information (OSTI), July 2016. http://dx.doi.org/10.2172/1561802.
Full text