Multipartite graph

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.

General Definition of k-partite graphs

A graph G is k-partite with vertex classes V₁,V₂,V₃,…,V_k if V(G)=V₁∪V₂∪V₃∪…∪V_k and V_i∩V_j=∅ whenever 1≤i<j≤k and no edge joins two vertices in the same class. 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.

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

The graph above is a complete tripartite graph, noted as K_(3,3,3). 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_(m,n,r), has the following properties:

1. The vertices can be partitioned into 3 subsets: M,N and R.
2. 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.

1. 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.

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 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.

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.