Heterogeneous Network Motifs

Abstract

Many real-world applications give rise to large heterogeneous networks where nodes and edges can be of any arbitrary type (e.g., user, web page, location). Special cases of such heterogeneous graphs include homogeneous graphs, bipartite, k-partite, signed, labeled graphs, among many others. In this work, we generalize the notion of network motifs to heterogeneous networks. In particular, small induced typed subgraphs called typed graphlets (heterogeneous network motifs) are introduced and shown to be the fundamental building blocks of complex heterogeneous networks. Typed graphlets are a powerful generalization of the notion of graphlet (network motif) to heterogeneous networks as they capture both the induced subgraph of interest and the types associated with the nodes in the induced subgraph. To address this problem, we propose a fast, parallel, and space-efficient framework for counting typed graphlets in large networks. We discover the existence of non-trivial combinatorial relationships between lower-order ($k-1$)-node typed graphlets and leverage them for deriving many of the $k$-node typed graphlets in $o(1)$ constant time. Thus, we avoid explicit enumeration of those typed graphlets. Notably, the time complexity matches the best untyped graphlet counting algorithm. The experiments demonstrate the effectiveness of the proposed framework in terms of runtime, space-efficiency, parallel speedup, and scalability as it is able to handle large-scale networks.

References in corpus (10)

• Community structure in social and biological networks
• Uncovering the overlapping community structure of complex networks in nature and society
• Defining and identifying communities in networks
• Higher-order organization of complex networks
• Biological network comparison using graphlet degree distribution
• Temporal motifs in time-dependent networks
• All-at-once Optimization for Coupled Matrix and Tensor Factorizations
• Learning Role-based Graph Embeddings
• HONE: Higher-Order Network Embeddings
• On Sampling from Massive Graph Streams

Cited by in corpus (5)

• Size-Invariant Graph Representations for Graph Classification Extrapolations
• Dynamic Node Embeddings from Edge Streams
• Efficiently Counting Vertex Orbits of All 5-vertex Subgraphs, by EVOKE
• Finding NeMo: Fishing in banking networks using network motifs
• Faster and Generalized Temporal Triangle Counting, via Degeneracy Ordering