Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Testing for Directed Information Graphs
KTH, School of Electrical Engineering and Computer Science (EECS), Centres, ACCESS Linnaeus Centre.ORCID iD: 0000-0002-6247-1217
KTH, School of Electrical Engineering and Computer Science (EECS), Centres, ACCESS Linnaeus Centre.
KTH, School of Electrical Engineering (EES), Centres, ACCESS Linnaeus Centre.ORCID iD: 0000-0002-7926-5081
2017 (English)In: 2017 55TH ANNUAL ALLERTON CONFERENCE ON COMMUNICATION, CONTROL, AND COMPUTING (ALLERTON), IEEE , 2017, p. 212-219Conference paper, Published paper (Refereed)
Abstract [en]

In this paper, we study a hypothesis test to determine the underlying directed graph structure of nodes in a network, where the nodes represent random processes and the direction of the links indicate a causal relationship between said processes. Specifically, a k-th order Markov structure is considered for them, and the chosen metric to determine a connection between nodes is the directed information. The hypothesis test is based on the empirically calculated transition probabilities which are used to estimate the directed information. For a single edge, it is proven that the detection probability can be chosen arbitrarily close to one, while the false alarm probability remains negligible. When the test is performed on the whole graph, we derive bounds for the false alarm and detection probabilities, which show that the test is asymptotically optimal by properly setting the threshold test and using a large number of samples. Furthermore, we study how the convergence of the measures relies on the existence of links in the true graph.

Place, publisher, year, edition, pages
IEEE , 2017. p. 212-219
Series
Annual Allerton Conference on Communication Control and Computing, ISSN 2474-0195
National Category
Probability Theory and Statistics
Identifiers
URN: urn:nbn:se:kth:diva-226276ISI: 000428047800030ISBN: 978-1-5386-3266-6 OAI: oai:DiVA.org:kth-226276DiVA, id: diva2:1198953
Conference
55th Annual Allerton Conference on Communication, Control, and Computing (Allerton), OCT 03-06, 2017, Monticello, IL
Note

QC 20180419

Available from: 2018-04-19 Created: 2018-04-19 Last updated: 2018-05-24Bibliographically approved

Open Access in DiVA

No full text in DiVA

Authority records BETA

Molavipour, SinaSkoglund, Mikael

Search in DiVA

By author/editor
Molavipour, SinaBassi, GermanSkoglund, Mikael
By organisation
ACCESS Linnaeus CentreACCESS Linnaeus Centre
Probability Theory and Statistics

Search outside of DiVA

GoogleGoogle Scholar

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf