A new method for determining dominant nodes in complex networks

The spread of socialization in digital environments has led to the production of huge amounts of digital data. Many social network analysis methods have been developed to extract useful patterns from these data. These analysis methods offer solutions for all types of problems that can be modeled in the social network structure. There are many types of problems in social networks that are complex to solve. These types of problems, expressed as NP-hard, are difficult problems that cannot be solved in polynomial time. The problem of determining the minimum dominant set on any network or graph is one of the popular NP-hard problems. There is no effective algorithm in the literature for determining the minimum dominant set. In the literature, there are algorithms with a greedy approach that provide approximate solutions and take a long time to solve to determine the minimum dominant set. In this thesis, an effective algorithm that produces near-optimal results is proposed to determine the minimum dominating set members defined as NP-hard problems in the literature. The proposed dominating set algorithm consists of two important stages. In the first stage, Karcı centrality algorithm which gives priority to selection in determining the dominant set members was developed. In the second stage, the selection algorithm that detects the dominating set members was developed. Karci centrality algorithm is used to calculate the dominance values of nodes in any graph. Karci centrality algorithm consists of 3 sub-algorithms. The first algorithm is used to construct the Karcı maximum tree (Kmax Tree ), which is a spanning tree. The second algorithm is used to calculate the cut-set degrees by considering the Kmax tree. As a result of these cut-set operations, the results of how much the nodes removed from the graph affect the network are determined. The third algorithm produces the Karci centrality (dominance) value, which is a combination of graph node degrees, Kmax node degrees, and cut-set degrees. Besides pagerank, eigenvector, betweenness and closeness centrality algorithms, which are popularly known in the literature, were applied to real world problems and their successes were examined with comparative results in the study. In another application, the Karci centrality algorithm, which was originally developed, and the pagerank, eigenvector, closeness, degree centrality algorithms were compared. It has been concluded that the Karci centrality algorithm shows partial similarities with other popular algorithms in the literature. All stages and pseudo-codes of the proposed algorithms are given in detail in the thesis study. Keywords: Graph theory, Dominant node, Karci centrality, Dominating set