One of the main advantages of AgentNet is that its computational complexity only depends on the node degree, the number of agents, and the number of steps. This means that if a specific graph problem does not require the entire graph to be observed, then our model can often solve it using less than \(n\)  operations, where \(n\)  is the number of nodes. The study of such sublinear algorithms is a popular topic in graph mining [1]}, [2]}; it is known that many relevant tasks can be solved in a sublinear manner. For example, our approach can recognize if one graph has more triangles than another, or estimate the frequency of certain substructures in the graph – in sublinear time!
