Method for finding the most prominent group of vertices in complex data communication networks

Shlomi Dolev, Yuval Elovici, Rami Puzis

. A searching method for finding the most influential group of vertices in a graph representing a data communication network, wherein vertices are routers connected to each other through communication lines, wherein the most influential group is a group of vertices that can inspect or modify most of the information flow in the data communication network; and wherein a Distributed Network Intrusion Detection System is deployed and monitors the traffic of the most influential group, the method being locating the group of vertices in the graph having the maximal Group Betweenness Centrality, GBC, the method comprising searching iteratively a decision tree for said group, wherein: a. each node C in said decision tree maintains one group of vertices, and an ordered list of candidate vertices, CL (C), each of which may be added to during said searching method; and b. said most influential group comprises k vertices, wherein k is a predetermined value; wherein at every node C the next best candidate vertex v∈ CL (C), determined according to the contribution of said vertex to the GBC of GM (C), is added to GM (C) until GM (C) contains k vertices. 2. The searching method of claim 1, wherein the decision tree is searched by a Depth First Branch and Bound (DFBnB) process by using: a. a first heuristic function, for determining the optimal order of the candidate vertices in wherein, once determined, the most influential vertex is first in and b. a second heuristic function, for estimating the maximal gain in GBC that can be acquired during the exploration of the sub-tree rooted at node C, wherein said decision tree is pruned according to said second heuristic …