A Solution to the Supernode Problem

In graph theory and network science, a supernode is a vertex with an unusually high number of incident edges. Supernodes are rare in natural graphs but appear frequently during graph analysis due to their connection to numerous paths. Graph computing can be affected by the presence of supernodes, leading to system performance problems. However, property graphs offer a theoretical and applied solution to this issue. Peer-to-peer networks often experience DoS attacks due to the existence of supernode clients that are quickly inundated with search requests. Twitter handles this discrepancy by maintaining different mechanisms for handling celebrities (supernodes) and ordinary users. Blueprints is a Java interface for graph-based software, which supports vertex queries through indexing incident edges by label or property. This allows efficient retrieval of data from massive graphs, such as those supported by the distributed graph database Titan. Vertex-centric indices can significantly improve query performance in activity stream-type systems and overcome the supernode problem by intelligently leveraging edge information.