Multipartite graph: Difference between revisions
Jamesx12345 (talk | contribs) m Jamesx12345 moved page Wikipedia talk:Articles for creation/Tripartite graphs and networks to Tripartite graphs and networks: Created via Articles for creation (you can help!) (AFCH) |
Jamesx12345 (talk | contribs) |
||
| Line 1: | Line 1: | ||
{{AFC submission|||ts=20130603005020|u=As acsi|ns=5}} |
|||
{{Network Science}} |
{{Network Science}} |
||
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>. |
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>. |
||
==General Definition of k-partite graphs== |
== General Definition of k-partite graphs == |
||
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> |
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> |
||
==Tripartite graphs == |
== Tripartite graphs == |
||
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 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. |
||
| Line 17: | Line 14: | ||
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. |
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=== |
=== 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.]] |
[[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.]] |
||
| Line 34: | Line 31: | ||
No vertex in R is connected to any other vertices in R. |
No vertex in R is connected to any other vertices in R. |
||
==The use of tripartite graphs in network science== |
== 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'''. |
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> |
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=== |
=== 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. |
[[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. |
||
| Line 49: | Line 46: | ||
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. |
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 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> |
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> |
||
| Line 55: | Line 52: | ||
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. |
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}} |
||
* |
* |
||
Revision as of 21:21, 11 June 2013
| Part of a series on | ||||
| Network science | ||||
|---|---|---|---|---|
| Network types | ||||
| Graphs | ||||
|
||||
| Models | ||||
|
||||
| ||||
In the mathematical field of graph theory, a tripartite graph is a graph whose vertices are partitioned into three sets (called partitions) in such a way that no two vertices contained in any one partition are adjacent[1].
General Definition of k-partite graphs
A graph G is k-partite with vertex classes V1,V2,V3,…,Vk if V(G)=V1∪V2∪V3∪…∪Vk and Vi∩Vj=∅ whenever 1≤i<j≤k and no edge joins two vertices in the same class.[2] 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. [3]
Tripartite graphs
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 three sets M,N and R may be thought of as a 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
A complete tripartite graph G, using the notation K(m,n,r), has the following properties[4]:
- 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 and then unipartite networks.[5]
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 Barabási[6] 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 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 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.[7]
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
- ^ http://www.edmath.org/MATtours/discrete/concepts/cbipar.html
- ^ Bollobas, B., Modern Graph Theory, 1998, Springer Science&Business Media INC, USA, page 6
- ^ Gross, J.L.; Yellen, J., Graph Theory and its applications, Second edition, 2006, Chapman and Hall, Boca Raton, USA, page 378
- ^ http://faculty.kutztown.edu/rieksts/225/graphs/tripartite.html
- ^ Lambiotte R., Ausloos M., Collaborative tagging as a tripartite network, SUPRATECS, Universite de Liege, 2005
- ^ 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).
- ^ 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