Jump to content

Multipartite graph: Difference between revisions

From Wikipedia, the free encyclopedia
Browse history interactively
← Previous edit
Content deleted Content added
VisualWikitext
Cleaning up the submission of afc (general cleanup) (bot)
No edit summary
 
(46 intermediate revisions by 21 users not shown)
Line 1: Line 1:
{{Short description|Graph able to be partitioned into multiple independent sets}}
{{AFC submission|||ts=20130603005020|u=As acsi|ns=5}}


In [[graph theory]], a part of mathematics, a '''{{mvar|k}}-partite graph''' is a [[Graph (discrete mathematics)|graph]] whose [[Vertex (graph theory)|vertices]] are (or can be) [[Graph partition|partitioned]] into {{mvar|k}} different [[independent set (graph theory)|independent sets]]. Equivalently, it is a graph that can be [[graph coloring|colored]] with {{mvar|k}} colors, so that no two endpoints of an edge have the same color. When {{math|1=''k'' = 2}} these are the [[bipartite graph]]s, and when {{math|1=''k'' = 3}} they are called the '''tripartite graphs'''.


Bipartite graphs may be recognized in [[polynomial time]] but, for any {{math|''k'' > 2}} it is [[NP-complete]], given an uncolored graph, to test whether it is {{mvar|k}}-partite.<ref>{{citation
{{AFC submission|t||ts=20130523214321|u=As acsi|ns=5}}
| last1 = Garey
{{Network Science}}
| first1 = M. R.
| author1-link = Michael R. Garey
| last2 = Johnson
| first2 = D. S.
| author2-link = David S. Johnson
| at = [https://archive.org/details/computersintract0000gare/page/ GT4]
| isbn = 0-7167-1045-5
| publisher = W.H. Freeman
| title = [[Computers and Intractability: A Guide to the Theory of NP-Completeness]]
| year = 1979
}}.</ref>
However, in some applications of graph theory, a {{mvar|k}}-partite graph may be given as input to a computation with its coloring already determined; this can happen when the sets of vertices in the graph represent different types of objects. For instance, [[folksonomy|folksonomies]] have been modeled mathematically by tripartite graphs in which the three sets of vertices in the graph represent users of a system, resources that the users are tagging, and tags that the users have applied to the resources.<ref>{{citation
| last1 = Hotho | first1 = Andreas
| last2 = Jäschke | first2 = Robert
| last3 = Schmitz | first3 = Christoph
| last4 = Stumme | first4 = Gerd
| contribution = FolkRank : A Ranking Algorithm for Folksonomies
| pages = 111–114
| title = LWA 2006: Lernen - Wissensentdeckung - Adaptivität, Hildesheim, October 9th-11th 2006
| url = http://opus.bsz-bw.de/ubhi/volltexte/2011/39/
| year = 2006}}.</ref>
{| class=wikitable align=right width=320
|+ Example complete {{mvar|k}}-partite graphs
!{{math|''K''{{sub|2,2,2}}}}
!{{math|''K''{{sub|3,3,3}}}}
!{{math|''K''{{sub|2,2,2,2}}}}
|- valign=top
|[[File:Complex_tripartite_graph_octahedron.svg|100px]]<BR>Graph of [[octahedron]]
|[[File:3-generalized-3-orthoplex-tripartite.svg|100px]]<BR>Graph of [[Cross-polytope#Generalized_orthoplex|complex generalized octahedron]]
|[[File:Complex_multipartite_graph_16-cell.svg|100px]]<BR>Graph of [[16-cell]]
|}


A '''complete {{mvar|k}}-partite graph''' is a {{mvar|k}}-partite graph in which there is an edge between every pair of vertices from different independent sets. These graphs are described by notation with a capital letter {{mvar|K}} subscripted by a sequence of the sizes of each set in the partition. For instance, {{math|''K''{{sub|2,2,2}}}} is the complete tripartite graph of a [[regular octahedron]], which can be partitioned into three independent sets each consisting of two opposite vertices. A '''complete multipartite graph''' is a graph that is complete {{mvar|k}}-partite for some {{mvar|k}}.<ref>{{citation
In the mathematical field of [[graph theory]], a '''tripartite graph''' is a [[graph]] whose [[Vertex (graph theory)|vertices]] are partitioned into three sets (called partitions) in such a way that no two vertices contained in any one partition are [[adjacent]]<ref>http://www.edmath.org/MATtours/discrete/concepts/cbipar.html</ref>.
| last1 = Chartrand | first1 = Gary | author1-link = Gary Chartrand

| last2 = Zhang | first2 = Ping | author2-link = Ping Zhang (graph theorist)
==General Definition of k-partite graphs==
| isbn = 9781584888017

| page = 41
A graph G is k-partite with vertex classes V<sub>1</sub>,V<sub>2</sub>,V<sub>3</sub>,…,V<sub>k</sub> if V(G)=V<sub>1</sub>∪V<sub>2</sub>∪V<sub>3</sub>∪…∪V<sub>k</sub> and V<sub>i</sub>∩V<sub>j</sub>=∅ whenever 1≤i<j≤k and no edge joins two vertices in the same class.<ref>Bollobas, B., Modern Graph Theory, 1998, Springer Science&Business Media INC, USA, page 6 </ref> This means that the vertices of the graph can be partitioned in k independent sets, which are sometimes called the partite sets of the partition. <ref>Gross, J.L.; Yellen, J., Graph Theory and its applications, Second edition, 2006, Chapman and Hall, Boca Raton, USA, page 378 </ref>
| publisher = CRC Press

| title = Chromatic Graph Theory
==Tripartite graphs ==
| url = https://books.google.com/books?id=_l4CJq46MXwC&pg=PA41

| year = 2008}}.</ref>
The tripartite graphs are the special case of k-partite graphs when k is equal with 3. This means that we can divide the vertices (nodes) of the graph in three independent sets (let's call them M,N and R) in such a way that every vertex in set M is connected only to vertices belonging to sets N and R, every vertex in set N is connected only to vertices belonging to sets M and R and every vertex in set R is connected only to vertices belonging to M and N.
The [[Turán graph]]s are the special case of complete multipartite graphs in which each two independent sets differ in size by at most one vertex.

Complete {{mvar|k}}-partite graphs, complete multipartite graphs, and their [[complement graph]]s, the [[cluster graph]]s, are special cases of [[cograph]]s, and can be recognized in polynomial time even when the partition is not supplied as part of the input.
The three sets M,N and R may be thought of as a [[graph coloring|coloring]] of the graph with three colors: if one colors all nodes in M blue, all nodes in N red and all nodes in R yellow, each edge will have endpoints of differing colors.

===Complete tripartite graphs===

[[File:Complete tripartite graph.jpg|thumbnail|The graph above is a complete tripartite graph, noted as K<sub>(3,3,3)</sub>. The set M is comprised of the blue vertices, N of the red vertices, and R of the yellow vertices. Every blue vertex is connected to all the yellow and red ones. Every red vertex is connected to all the yellow and blue ones. Every yellow vertex is connected to all the blue and red ones.]]
A complete tripartite graph G, using the notation K<sub>(m,n,r)</sub>, has the following properties<ref>http://faculty.kutztown.edu/rieksts/225/graphs/tripartite.html</ref>:
#The vertices can be partitioned into 3 subsets: M,N and R.
#Each vertex in M is connected to all vertices in N and R.

Each vertex in N is connected to all vertices in in M and R.

Each vertex in R is connected to all vertices in M and N.
#No vertex in M is connected to any other vertices in M.

No vertex in N is connected to any other vertices in N.

No vertex in R is connected to any other vertices in R.

==The use of tripartite graphs in network science==

Tripartite graphs are used in [[network science]] for modelling a particular class of [[complex networks]], whose nodes are divided into three sets and only connections between two nodes in different sets are allowed. These networks are called '''tripartite networks'''.
The most usual way of simplification of the analysis of multi-partite networks consists in projecting them on lower order networks -in this case [[Bipartite network projection|bipartite]] and then unipartite networks.<ref>Lambiotte R., Ausloos M., Collaborative tagging as a tripartite network, SUPRATECS, Universite de Liege, 2005</ref>

===Flavor network and the principals of food pairing===

[[Foodpairing]] is a method for identifying which foods go well together. The method is based on the principle that foods combine well with one another when they share key flavor components. In their study Ahn, Ahnert, Bagrow and [[Albert-László Barabási|Barabási]]<ref>Ahn, Y.-Y., Ahnert, S.E., Bagrow, J.P. & Barabási, A.-L. Flavor network and the principles of food pairing. Sci. Rep. 1, 196; DOI:10.1038/srep00196 (2011).</ref> introduce a flavor network that captures the flavor compounds shared by culinary ingredients. They find out that Western cuisines tend to use ingredient pairs that share many flavor compounds (this is in line with the “food pairing hypothesis”) while East Asian cuisines show a tendency to avoid compound sharing ingredients. The food pairing hypothesis says that ingredients sharing flavor compounds are more likely to taste well together than ingredients that do not.
They introduce a network-based approach to explore the impact of flavor compounds in ingredient combinations (i.e. dishes). First they link each ingredient to 51 flavor compounds and build a bipartite network consisting of two different types of nodes: 381 ingredients used in recipes throughout the world, and 1,021 flavor compounds that are known to contribute to the flavor of each of these ingredients. A [[Bipartite network projection|projection of this bipartite network]] is the flavor network in which two nodes (ingredients) are connected if they share at least one flavor compound.

In order to test the food pairing hypothesis, they transform the bipartite network into a tripartite network by adding 56,498 recipes to the network. Now there are three different types of nodes: 381 ingredients, 1021 flavor compounds and 56498 recipes. Recipies are basically combinations of ingredients so the nodes represented by recipies have links to different ingredients. The different ingredients have links to the different flavor compounds. Through this we can make links between dishes (recipes) and flavor compounds.

They find out that the average number of ingredients used in a recipe is approximately eight and recipes with a very large or very small number of ingredients are rare. On the contrary, the popularity of specific ingredients has huge variations. While egg appears in more than 20 thousand recipes, jasmine tea, Jamaican Rum and 14 other ingredients each appear in only one single recipe.
Based on the analysis of the tripartite network built, their main finding is that North American and Western European cuisines exhibit a statistically significant tendency towards recipes whose ingredients share flavor compounds and by contrast, East Asian and Southern European cuisines avoid recipes whose ingredients share flavor compounds. They further generalize the food pairing hypothesis by exploring if ingredient pairs sharing more compounds are more likely to be used in specific cuisines. The results are in line with those stated above: in North American recipes, the more compounds are shared by two ingredients, the more likely they appear in recipes. By contrast, in East Asian cuisine the more flavor compounds two ingredients share, the less likely they are used together. This suggests that the food pairing effect is due to a few outliers that are frequently used in a particular cuisine, e.g. milk, butter, cocoa, vanilla, cream, and egg in the North America, and beef, ginger, pork, cayenne, chicken, and onion in East Asia.

===The tripartite network of social tagging===

The phenomena of [[Folksonomy|Social tagging]] started with the appearance of the [[Web 2.0]]. Social tagging systems make it possible for users to annotate on-line resources with free-form tags. The resources can be of any type or in any format, for example web-pages, videos, photos and so on. All the social tagging systems have the common purpose of helping users share, store, organize and retrieve the resources they are interested in.<ref>Lu C., Chen X., Park E.K., Exploit the Tripartite Network of Social Tagging for Web Clustering, http://www.academia.edu/215105/Exploit_the_Tripartite_Network_of_Social_Tagging_for_Web_Clustering </ref>

We can look at social tagging systems as tripartite networks formed of three different kind of nodes: users, resources and tags. Once a user applies a tag to a resource, a new link forms between the user and the resource, the user and the tag and the resource and the tag. These tripartite networks are analyzed by network scientists for detecting communities.


==References==
==References==
{{reflist}}
{{reflist}}
*
*
*
*

<!-- This will add a notice to the bottom of the page and won't blank it! The new template which says that your draft is waiting for a review will appear at the bottom; simply ignore the old (grey) drafted templates and the old (red) decline templates. A bot will update your article submission. Until then, please don't change anything in this text box. Just press "Save page". -->



[[Category:Graph families]]
<!-- This will add a notice to the bottom of the page and won't blank it! The new template which says that your draft is waiting for a review will appear at the bottom; simply ignore the old (grey) drafted templates and the old (red) decline templates. A bot will update your article submission. Until then, please don't change anything in this text box. Just press "Save page". -->
[[Category:NP-complete problems]]

Latest revision as of 08:07, 16 July 2024

In graph theory, a part of mathematics, a k-partite graph is a graph whose vertices are (or can be) partitioned into k different independent sets. Equivalently, it is a graph that can be colored with k colors, so that no two endpoints of an edge have the same color. When k = 2 these are the bipartite graphs, and when k = 3 they are called the tripartite graphs.

Bipartite graphs may be recognized in polynomial time but, for any k > 2 it is NP-complete, given an uncolored graph, to test whether it is k-partite.[1] However, in some applications of graph theory, a k-partite graph may be given as input to a computation with its coloring already determined; this can happen when the sets of vertices in the graph represent different types of objects. For instance, folksonomies have been modeled mathematically by tripartite graphs in which the three sets of vertices in the graph represent users of a system, resources that the users are tagging, and tags that the users have applied to the resources.[2]

Example complete k-partite graphs
K2,2,2 K3,3,3 K2,2,2,2

Graph of octahedron
Graph of complex generalized octahedron
Graph of 16-cell

A complete k-partite graph is a k-partite graph in which there is an edge between every pair of vertices from different independent sets. These graphs are described by notation with a capital letter K subscripted by a sequence of the sizes of each set in the partition. For instance, K2,2,2 is the complete tripartite graph of a regular octahedron, which can be partitioned into three independent sets each consisting of two opposite vertices. A complete multipartite graph is a graph that is complete k-partite for some k.[3] The Turán graphs are the special case of complete multipartite graphs in which each two independent sets differ in size by at most one vertex. Complete k-partite graphs, complete multipartite graphs, and their complement graphs, the cluster graphs, are special cases of cographs, and can be recognized in polynomial time even when the partition is not supplied as part of the input.

References

[edit]
  1. ^ Garey, M. R.; Johnson, D. S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, GT4, ISBN 0-7167-1045-5.
  2. ^ Hotho, Andreas; Jäschke, Robert; Schmitz, Christoph; Stumme, Gerd (2006), "FolkRank : A Ranking Algorithm for Folksonomies", LWA 2006: Lernen - Wissensentdeckung - Adaptivität, Hildesheim, October 9th-11th 2006, pp. 111–114.
  3. ^ Chartrand, Gary; Zhang, Ping (2008), Chromatic Graph Theory, CRC Press, p. 41, ISBN 9781584888017.
Retrieved from "https://en.wikipedia.org/enwiki/w/index.php?title=Multipartite_graph&oldid=1234813170"