In the recent world of social networks and big data, the investigation of graph structures representing relationships between components of large datasets is a practically relevant and scientifically interesting question. The main aim of these approaches is to discover a model of datasets to give a structure of the chaotic interconnections between data elements. An interesting issue to explore is the hierarchy of data elements that can be represented by arbitrary graph structures, as social networks, real hierarchy within organizations, surfing on the Internet, and so on. The typical basic approach is to use some ranking systems among the nodes along with considering specific properties of vertices, for example, weights, and applying adequate algorithms.
The paper is not for readers lacking deep mathematical knowledge of graph theory. It appeared in a peer-reviewed journal (however, it contains several annoying spelling errors), so the validity of the algorithms and the estimation of their complexity can be regarded as correct.
The author describes an extension and improvement of algorithms that can find the hierarchy within graphs (directed acyclic graph, DAG) with disparate preconditions. The original idea of these algorithms can be followed back to minimal cost flow problems within graphs [1].
Primarily in the social networks environment, the vertices are ranked by a specific function reflecting the status of the incoming and outgoing links; the vertices that belong to a hierarchy acquire zero penalty, vertices that do not conform with the hierarchy but have elements of the same group may get one penalty point, and so on. Edges that go from lower ranked vertices to higher ranked vertices are more frequent than the other way around. The edges that point backwards, that is, from higher ranked vertices to lower ranked ones, cause “agony.” Interestingly, this notion of agony can be used for locating hierarchies within graphs. Naturally, this concept is not enough, but the other complex notion and definition can be found in the paper (for example, circulation graphs).
The author exploits several previously defined algorithms for discovering hierarchies in graphs, and creates an extended and improved version. The feasibility and viability of the proposed algorithm are proven through the experimental running of algorithms on the selected datasets. The main goal was to find polynomial-time algorithms. Intriguingly, the algorithm complexity is dependent on the mathematical properties of the selected penalty function. In the case of convex function, the algorithm complexity is polynomial in time; in the case of concave function, the complexity is NP-hard in time. The experimental execution of the proposed algorithm supports the estimated complexity; the running time of the proposed algorithm with certain parameters seems to be practically reasonable, and the algorithm can be used in practice.
The paper is very long and requires deep knowledge in graph and algorithm theory, but it is an interesting contribution to the algorithmic analysis of datasets that can be represented in graph formats; furthermore, an understanding of the internal structure of the dataset is important for model creation, for example, whether the dataset has a hierarchical structure or not. Researchers who are involved in data science and big data analytics may find the algorithms described in the paper interesting.
