What graphs are 2-dot product graphs?

DOI10.1016/J.ENDM.2015.06.095MaRDI QIDQ322356zbMATHOpenAlexFDO

Authors Matthew Johnson, Erik Jan van Leeuwen, Daniël Paulusma

Publication date 14 October 2016

Full work available at URL https://arxiv.org/abs/1511.05009

zbMATH Keywords

social networksgraph classesdot product graphs

Mathematics Subject Classification ID

Social networks; opinion dynamics (91D30) Graph operations (line graphs, products, etc.) (05C76)

Abstract: Let $dgeq1$ be an integer. From a set of $d$-dimensional vectors, we obtain a $d$-dpg by letting each vector $v{a}^u$ correspond to a vertex $u$ and by adding an edge between two vertices $u$ and $v$ if and only if their dot product $v{a}^{u}cdotv{a}^{v}geqt$, for some fixed, positive threshold~$t$. Dot product graphs can be used to model social networks. Recognizing a $d$-dot product graph is known to be NP-hard for all fixed $dgeq2$. To understand the position of $d$-dot product graphs in the landscape of graph classes, we consider the case $d=2$, and investigate how $2$-dot product graphs relate to a number of other known graph classes including a number of well-known classes of intersection graphs.

Recommendations

• Dot product representations of graphs
• Random Dot Product Graph Models for Social Networks
• Dot product representations of planar graphs
• Dot product representations of planar graphs
• Algorithms to measure diversity and clustering in social networks through dot product graphs

Cites work

• scientific article; zbMATH DE number 1224949 (Why is no real title available?)
• Directed Random Dot Product Graphs
• Dot product dimensions of graphs
• Dot product representations of graphs
• Dot product representations of planar graphs
• Kronecker graphs: an approach to modeling networks
• Latent Space Approaches to Social Network Analysis
• Modeling graphs using dot product representations
• Random Dot Product Graph Models for Social Networks
• Sphere and dot product representations of graphs

Cited in

(4)

• Dot product dimensions of graphs
• What Graphs are 2-Dot Product Graphs?
• Algorithms to measure diversity and clustering in social networks through dot product graphs
• Dot product dimension of unicyclic graphs

Describes a project that uses

Uses Software

• KronFit

This page was built for publication: What graphs are 2-dot product graphs?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q322356)