A Random Walk-Based Approach for Clustering of Food Items

Most of the recipe sites have a distinct page structure comprising a title, list of ingredients, preparation instructions, comments, and thus it is very challenging to cluster similar recipes. The work presented here initially starts with the formation of a recipe network and finding ‘leading’ nodes from the network. To the best of our knowledge, there doesn’t exist any research that addresses the concept of finding ‘leading’ nodes from a recipe network and subsequently clustering similar recipes based on the ingredients. In order to fill this gap, we have proposed a method RWRC (Random Walk-based Recipe Clustering). To determine the ‘leading’ nodes, the proposed approach incorporates data from the breadth-first search tree. To create a breadth-first search (BFS) tree, the graph is explored in level-order, starting with each node as the root node. At each level of the traversal, we have computed the degree centrality, betweenness centrality and closeness centrality of each node. The ‘leading factor’ has been considered as the average of these centrality measures for all the nodes present in the network. A random walk-based graph clustering approach has been addressed that initiates from the root node of the original recipe network. If the ‘leading factor’ of the next visiting node in the random walk is equal to or greater than the average ‘leading factor’ of the whole network, the agent moves to its neighbours; otherwise, the stopping requirement is satisfied. Further, these nodes discovered by this random walk are organised into a cluster. When a walk comes to an end, the visited nodes from the initial graph are extracted, and the subsequent walk begins in the remaining graph. The random walk continues until there are no undiscovered node(s) left. These extracted nodes form the clusters of recipes.