Role Discovery in Networks
arXiv:1405.7134 · doi:10.1109/TKDE.2014.2349913
Abstract
Roles represent node-level connectivity patterns such as star-center, star-edge nodes, near-cliques or nodes that act as bridges to different regions of the graph. Intuitively, two nodes belong to the same role if they are structurally similar. Roles have been mainly of interest to sociologists, but more recently, roles have become increasingly useful in other domains. Traditionally, the notion of roles were defined based on graph equivalences such as structural, regular, and stochastic equivalences. We briefly revisit these early notions and instead propose a more general formulation of roles based on the similarity of a feature representation (in contrast to the graph representation). This leads us to propose a taxonomy of three general classes of techniques for discovering roles that includes (i) graph-based roles, (ii) feature-based roles, and (iii) hybrid roles. We also propose a flexible framework for discovering roles using the notion of similarity on a feature-based representation. The framework consists of two fundamental components: (a) role feature construction and (b) role assignment using the learned feature representation. We discuss the different possibilities for discovering feature-based roles and the tradeoffs of the many techniques for computing them. Finally, we discuss potential applications and future directions and challenges.
Published in IEEE TKDE. Manuscript received Jan. 7, 2014; revised July 10, 2014; accepted July 29, 2014. Date of publication Aug. 19, 2014
References in corpus (4)
Cited by in corpus (41)
- REGAL: Representation Learning-based Graph Alignment
- Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning
- Detection of Core-Periphery Structure in Networks Using Spectral Methods and Geodesic Paths
- On Proximity and Structural Role-based Embeddings in Networks: Misconceptions, Techniques, and Applications
- Learning Role-based Graph Embeddings
- A Framework for the Construction of Generative Models for Mesoscale Structure in Multilayer Networks
- Mesoscale analyses of fungal networks as an approach for quantifying phenotypic traits
- Deep Feature Learning for Graphs
- MILE: A Multi-Level Framework for Scalable Graph Embedding
- Adapting Stochastic Block Models to Power-Law Degree Distributions
- Panther: Fast Top-k Similarity Search in Large Networks
- Inductive Representation Learning in Large Attributed Graphs
- Deep Learning for Learning Graph Representations
- A Framework for Generalizing Graph-based Representation Learning Methods
- HONE: Higher-Order Network Embeddings
- Estimation of Graphlet Statistics
- Deep Graph Similarity Learning: A Survey
- Node-Centric Graph Learning from Data for Brain State Identification
- Entity Profiling in Knowledge Graphs
- On Sampling from Massive Graph Streams
- Inference of Edge Correlations in Multilayer Networks
- From acquaintance to best friend forever: robust and fine-grained inference of social tie strengths
- SPINE: Structural Identity Preserved Inductive Network Embedding
- Dynamic Node Embeddings from Edge Streams
- Role-Aware Modeling for N-ary Relational Knowledge Bases
- Social Catalysts: Characterizing People Who Spark Conversations Among Others
- Stochastic Block Models are a Discrete Surface Tension
- Latent Network Summarization: Bridging Network Embedding and Summarization
- Predicting Graph Categories from Structural Properties
- Revisiting Role Discovery in Networks: From Node to Edge Roles
- A sampling framework for counting temporal motifs
- Temporal Network Sampling
- Contrast Subgraph Mining from Coherent Cores
- From Static to Dynamic Node Embeddings
- Nodal statistics-based equivalence relation for graph collections
- PanRep: Graph neural networks for extracting universal node embeddings in heterogeneous graphs
- MLANE: Meta-Learning Based Adaptive Network Embedding
- A Web-based Interactive Visual Graph Analytics Platform
- Network Cartography: Seeing the Forest and the Trees
- On The Network You Keep: Analyzing Persons of Interest using Cliqster
- A Survey on Role-Oriented Network Embedding