top of page

Breadth First Search improvements (BFS) in Trovares Release 1.13.0

Updated: Feb 13

One of the most common whole graph algorithms, BFS searches a graph starting from a set of source vertices and explores vertices and edges in increasing order of distance from the sources. Trovares 1.12 returns the edges that form the BFS tree, which are the edges where the search discovers a new vertex. This allows a user to find the set of unique vertices reachable from the source vertices, possibly limited by searching only k hops from the sources. As requested by a customer, Trovares 1.13 adds the ability to return all the edges encountered by the search. This allows a user to find all the unique edges reachable from a set of source vertices in addition to the set of unique vertices.

BFS is often used in credit card fraud applications. One common usage of BFS is when a set of vertices representing actors of interest is known and an analyst wants to explore the graph near those actors. Sometimes an analyst may only be interested in other actors near the actors of interest. In this case the 1.12 behavior described above was enough. Sometimes, though, an analyst wants to see actors near the actors of interest along with all the connections between them. 1.13 adds the latter capability.

bottom of page