Extending Degree Based Search Algorithm for All Directed Disconnected Graphs

Graph traversal is a fundamental process in numerous applications, including citation analysis, influence maximization, and recommendation systems. Standard traversal methods—Breadth-First Search (BFS) and Depth-First Search (DFS)—exhibit performance limitations when applied to large, unconnected, or directed graphs, particularly when the objective is to identify influential nodes efficiently. In this research, we present a novel graph traversal strategy termed Degree-Based Search (DBS), which prioritizes nodes using a tunable score P(v) = α deg-(v) + β deg4(v) with α + β = 1 to flexibly emphasize authorities (in-degree) or hubs (out-degree). By ranking nodes in descending order of this score, DBS enables early discovery of high-impact nodes across disconnected components. The computational complexity of the method is O((|V|+|E|) log |V|), where |V| and |E| denote the number of vertices and edges, respectively. Empirical evaluation on the Cora citation dataset shows that DBS-1.00 (α = 1.0) outperformed BFS and DFS by identifying the top 10 most-cited nodes with only 45.6% graph traversal and locating the top 20 nodes at an average position of 13.3%, compared to 64.3% and over 23% for BFS and DFS, respectively. The tunability of DBS makes it especially effective in applications such as biological networks and social media graphs, where influential hubs and authorities play central roles in information flow.