Node ordering for rescalable network summarization (or, the apparent magic of word frequency and age of acquisition in the Lexicon)

Violet Brown; Xi Chen; Maryam Hedayati; Camden Sikes; Julia Strand; Tegan Wilson; David Liben-Nowell

doi:10.1007/978-3-030-05411-3_6

Node ordering for rescalable network summarization (or, the apparent magic of word frequency and age of acquisition in the Lexicon)

Violet Brown
, Xi Chen
, Maryam Hedayati
, Camden Sikes
, Julia Strand
, Tegan Wilson
, David Liben-Nowell

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

How can we “scale down” an n-node network G to a smaller network G, with k « n nodes, so that G' (approximately) maintains the important structural properties of G? There is a voluminous literature on many versions of this problem if k is given in advance, but one’s tolerance for approximation (and the resulting value of k) will vary. Here, then, we formulate a “rescalable” version of this approximation task for complex networks. Specifically, we propose a node ordering version of graph summarization: permute the nodes of G so that the subgraph induced by the first k nodes is a good size-k approximation of G, averaged over the full range of possible sizes k. We consider as a case study the phonological network of English words, and discover two natural word orders (word frequency and age of acquisition) that do a surprisingly good job of rescalably summarizing the lexicon.

Original language	English (US)
Title of host publication	Complex Networks and Their Applications VII - Volume 1 Proceedings The 7th International Conference on Complex Networks and their Applications COMPLEX NETWORKS 2018
Editors	Renaud Lambiotte, Luis M. Rocha, Pietro Lió, Hocine Cherifi, Luca Maria Aiello, Chantal Cherifi
Publisher	Springer Verlag
Pages	66-80
Number of pages	15
ISBN (Print)	9783030054106
DOIs	https://doi.org/10.1007/978-3-030-05411-3_6
State	Published - 2019
Externally published	Yes
Event	7th International Conference on Complex Networks and their Applications, COMPLEX NETWORKS 2018 - Cambridge, United Kingdom Duration: Dec 11 2018 → Dec 13 2018

Publication series

Name	Studies in Computational Intelligence
Volume	812
ISSN (Print)	1860-949X

Conference

Conference	7th International Conference on Complex Networks and their Applications, COMPLEX NETWORKS 2018
Country/Territory	United Kingdom
City	Cambridge
Period	12/11/18 → 12/13/18

All Science Journal Classification (ASJC) codes

Artificial Intelligence

Keywords

Network summarization
Node ordering
Phonological networks

Access to Document

10.1007/978-3-030-05411-3_6

Cite this

Brown, V., Chen, X., Hedayati, M., Sikes, C., Strand, J., Wilson, T., & Liben-Nowell, D. (2019). Node ordering for rescalable network summarization (or, the apparent magic of word frequency and age of acquisition in the Lexicon). In R. Lambiotte, L. M. Rocha, P. Lió, H. Cherifi, L. M. Aiello, & C. Cherifi (Eds.), Complex Networks and Their Applications VII - Volume 1 Proceedings The 7th International Conference on Complex Networks and their Applications COMPLEX NETWORKS 2018 (pp. 66-80). (Studies in Computational Intelligence; Vol. 812). Springer Verlag. https://doi.org/10.1007/978-3-030-05411-3_6

Brown, Violet ; Chen, Xi ; Hedayati, Maryam et al. / Node ordering for rescalable network summarization (or, the apparent magic of word frequency and age of acquisition in the Lexicon). Complex Networks and Their Applications VII - Volume 1 Proceedings The 7th International Conference on Complex Networks and their Applications COMPLEX NETWORKS 2018. editor / Renaud Lambiotte ; Luis M. Rocha ; Pietro Lió ; Hocine Cherifi ; Luca Maria Aiello ; Chantal Cherifi. Springer Verlag, 2019. pp. 66-80 (Studies in Computational Intelligence).

@inproceedings{4c6f0cac5ada4af9bdce9271887fba4e,

title = "Node ordering for rescalable network summarization (or, the apparent magic of word frequency and age of acquisition in the Lexicon)",

abstract = "How can we “scale down” an n-node network G to a smaller network G, with k « n nodes, so that G' (approximately) maintains the important structural properties of G? There is a voluminous literature on many versions of this problem if k is given in advance, but one{\textquoteright}s tolerance for approximation (and the resulting value of k) will vary. Here, then, we formulate a “rescalable” version of this approximation task for complex networks. Specifically, we propose a node ordering version of graph summarization: permute the nodes of G so that the subgraph induced by the first k nodes is a good size-k approximation of G, averaged over the full range of possible sizes k. We consider as a case study the phonological network of English words, and discover two natural word orders (word frequency and age of acquisition) that do a surprisingly good job of rescalably summarizing the lexicon.",

keywords = "Network summarization, Node ordering, Phonological networks",

author = "Violet Brown and Xi Chen and Maryam Hedayati and Camden Sikes and Julia Strand and Tegan Wilson and David Liben-Nowell",

note = "Publisher Copyright: {\textcopyright} 2019, Springer Nature Switzerland AG.; 7th International Conference on Complex Networks and their Applications, COMPLEX NETWORKS 2018 ; Conference date: 11-12-2018 Through 13-12-2018",

year = "2019",

doi = "10.1007/978-3-030-05411-3\_6",

language = "English (US)",

isbn = "9783030054106",

series = "Studies in Computational Intelligence",

publisher = "Springer Verlag",

pages = "66--80",

editor = "Renaud Lambiotte and Rocha, \{Luis M.\} and Pietro Li{\'o} and Hocine Cherifi and Aiello, \{Luca Maria\} and Chantal Cherifi",

booktitle = "Complex Networks and Their Applications VII - Volume 1 Proceedings The 7th International Conference on Complex Networks and their Applications COMPLEX NETWORKS 2018",

address = "Germany",

}

Brown, V, Chen, X, Hedayati, M, Sikes, C, Strand, J, Wilson, T & Liben-Nowell, D 2019, Node ordering for rescalable network summarization (or, the apparent magic of word frequency and age of acquisition in the Lexicon). in R Lambiotte, LM Rocha, P Lió, H Cherifi, LM Aiello & C Cherifi (eds), Complex Networks and Their Applications VII - Volume 1 Proceedings The 7th International Conference on Complex Networks and their Applications COMPLEX NETWORKS 2018. Studies in Computational Intelligence, vol. 812, Springer Verlag, pp. 66-80, 7th International Conference on Complex Networks and their Applications, COMPLEX NETWORKS 2018, Cambridge, United Kingdom, 12/11/18. https://doi.org/10.1007/978-3-030-05411-3_6

Node ordering for rescalable network summarization (or, the apparent magic of word frequency and age of acquisition in the Lexicon). / Brown, Violet; Chen, Xi; Hedayati, Maryam et al.
Complex Networks and Their Applications VII - Volume 1 Proceedings The 7th International Conference on Complex Networks and their Applications COMPLEX NETWORKS 2018. ed. / Renaud Lambiotte; Luis M. Rocha; Pietro Lió; Hocine Cherifi; Luca Maria Aiello; Chantal Cherifi. Springer Verlag, 2019. p. 66-80 (Studies in Computational Intelligence; Vol. 812).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Node ordering for rescalable network summarization (or, the apparent magic of word frequency and age of acquisition in the Lexicon)

AU - Brown, Violet

AU - Chen, Xi

AU - Hedayati, Maryam

AU - Sikes, Camden

AU - Strand, Julia

AU - Wilson, Tegan

AU - Liben-Nowell, David

PY - 2019

Y1 - 2019

N2 - How can we “scale down” an n-node network G to a smaller network G, with k « n nodes, so that G' (approximately) maintains the important structural properties of G? There is a voluminous literature on many versions of this problem if k is given in advance, but one’s tolerance for approximation (and the resulting value of k) will vary. Here, then, we formulate a “rescalable” version of this approximation task for complex networks. Specifically, we propose a node ordering version of graph summarization: permute the nodes of G so that the subgraph induced by the first k nodes is a good size-k approximation of G, averaged over the full range of possible sizes k. We consider as a case study the phonological network of English words, and discover two natural word orders (word frequency and age of acquisition) that do a surprisingly good job of rescalably summarizing the lexicon.

AB - How can we “scale down” an n-node network G to a smaller network G, with k « n nodes, so that G' (approximately) maintains the important structural properties of G? There is a voluminous literature on many versions of this problem if k is given in advance, but one’s tolerance for approximation (and the resulting value of k) will vary. Here, then, we formulate a “rescalable” version of this approximation task for complex networks. Specifically, we propose a node ordering version of graph summarization: permute the nodes of G so that the subgraph induced by the first k nodes is a good size-k approximation of G, averaged over the full range of possible sizes k. We consider as a case study the phonological network of English words, and discover two natural word orders (word frequency and age of acquisition) that do a surprisingly good job of rescalably summarizing the lexicon.

KW - Network summarization

KW - Node ordering

KW - Phonological networks

UR - https://www.scopus.com/pages/publications/85059093943

UR - https://www.scopus.com/pages/publications/85059093943#tab=citedBy

U2 - 10.1007/978-3-030-05411-3_6

DO - 10.1007/978-3-030-05411-3_6

M3 - Conference contribution

AN - SCOPUS:85059093943

SN - 9783030054106

T3 - Studies in Computational Intelligence

SP - 66

EP - 80

BT - Complex Networks and Their Applications VII - Volume 1 Proceedings The 7th International Conference on Complex Networks and their Applications COMPLEX NETWORKS 2018

A2 - Lambiotte, Renaud

A2 - Rocha, Luis M.

A2 - Lió, Pietro

A2 - Cherifi, Hocine

A2 - Aiello, Luca Maria

A2 - Cherifi, Chantal

PB - Springer Verlag

T2 - 7th International Conference on Complex Networks and their Applications, COMPLEX NETWORKS 2018

Y2 - 11 December 2018 through 13 December 2018

ER -

Brown V, Chen X, Hedayati M, Sikes C, Strand J, Wilson T et al. Node ordering for rescalable network summarization (or, the apparent magic of word frequency and age of acquisition in the Lexicon). In Lambiotte R, Rocha LM, Lió P, Cherifi H, Aiello LM, Cherifi C, editors, Complex Networks and Their Applications VII - Volume 1 Proceedings The 7th International Conference on Complex Networks and their Applications COMPLEX NETWORKS 2018. Springer Verlag. 2019. p. 66-80. (Studies in Computational Intelligence). doi: 10.1007/978-3-030-05411-3_6

Node ordering for rescalable network summarization (or, the apparent magic of word frequency and age of acquisition in the Lexicon)

Abstract

Publication series

Conference

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this