TY - GEN

T1 - Directed Intersection Representations and the Information Content of Digraphs

AU - Kostochka, Alexandr V.

AU - Liu, Xujun

AU - Machado, Roberto

AU - Milenkovic, Olgica

N1 - Funding Information:
ACKNOWLEDGMENT The work was supported by the NSF STC Center for Science of Information, 4101-38050, the São Paulo Research Foundation grant 2015/11286-8, UIUC Research Board Grant RB17164, the grant NSF CCF 15-26875 and DMS-1600592, and grants 18-01-00353A and 16-01-00499 of the Russian Foundation for Basic Research.

PY - 2019/7

Y1 - 2019/7

N2 - Consider a directed graph (digraph) in which two user vertices are connected if and only if they share at least one unit of common information content and the head vertex has a strictly smaller content than the tail. We seek to estimate the smallest possible global information content that can explain the observed digraph topology. To address this problem, we introduce the new notion of a directed intersection representation of a digraph, and show that it is well-defined for all directed acyclic graphs (DAGs). We then proceed to describe the directed intersection number (DIN), the smallest number of information units needed to represent the DAG. Our main result is a nontrivial upper bound on the DIN number of DAGs based on the longest terminal path decomposition of the vertex set. In addition, we compute the exact values of the DIN number for several simple yet relevant families of connected DAGs and construct digraphs that have near-optimal DIN values.

AB - Consider a directed graph (digraph) in which two user vertices are connected if and only if they share at least one unit of common information content and the head vertex has a strictly smaller content than the tail. We seek to estimate the smallest possible global information content that can explain the observed digraph topology. To address this problem, we introduce the new notion of a directed intersection representation of a digraph, and show that it is well-defined for all directed acyclic graphs (DAGs). We then proceed to describe the directed intersection number (DIN), the smallest number of information units needed to represent the DAG. Our main result is a nontrivial upper bound on the DIN number of DAGs based on the longest terminal path decomposition of the vertex set. In addition, we compute the exact values of the DIN number for several simple yet relevant families of connected DAGs and construct digraphs that have near-optimal DIN values.

UR - http://www.scopus.com/inward/record.url?scp=85073143872&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85073143872&partnerID=8YFLogxK

U2 - 10.1109/ISIT.2019.8849253

DO - 10.1109/ISIT.2019.8849253

M3 - Conference contribution

AN - SCOPUS:85073143872

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 1477

EP - 1481

BT - 2019 IEEE International Symposium on Information Theory, ISIT 2019 - Proceedings

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2019 IEEE International Symposium on Information Theory, ISIT 2019

Y2 - 7 July 2019 through 12 July 2019

ER -