History of Network Science
The birth of graph theory
The Seven Bridges of Königsberg Problem: Is it possible to only cross each bridge once while visiting all islands?
History of Network Science
The birth of graph theory
The Seven Bridges of Königsberg Problem: Is it possible to only cross each bridge once while visiting all islands?
Euler showed that there was no solution. He showed this by developing a new technique for analyzing networks (graph theory).
What is a network and why is it cool
Networks are simple.
- they are made up of two components: Nodes and Edges
- nodes/vertices = individual units
- edges/links/connections = relationships between units
Networks are everywhere (once you know what to look for).
- biological, economic, communication, technological, social, cultural networks
Network of the internet, Mark Newman
What is a network and why is it cool
Networks are useful.
- networks reveal patterns in systems
- networks describe relationships and interactions
- networks can predict "behaviors" or processes of the system
Networks are powerful.
- when combined with mathematical and discipline-specific theory, computing resources, and availability of big data
Social network of LOTR characters.
The Building Blocks of Networks
All networks have the following:
- a set of nodes
- nodes = vertices
- a set of relations between the nodes
- edges = links = connections
Representational formats
- graphical approaches
- pros: intuitive, visually compelling
- cons: cannot do much with a picture
- mathematical representations
- pros: very powerful and informative because of its explicitness
- cons: looks scary to people
network <- matrix( data = sample(0:1, size = 25, replace = TRUE), nrow = 5, ncol = 5)network## [,1] [,2] [,3] [,4] [,5]## [1,] 1 1 1 0 0## [2,] 1 1 1 1 1## [3,] 0 0 1 0 1## [4,] 1 0 1 0 1## [5,] 0 1 0 1 0Adjacency Matrix
Each row/column = 1 node
Each cell = presence or absence of edge
## 1 2 3 4 5 6 7 8 9 10## 1 0 1 0 0 1 1 0 0 0 0## 2 1 0 0 0 0 0 1 0 0 0## 3 0 0 0 1 0 0 0 1 0 0## 4 0 0 1 0 1 0 0 0 0 0## 5 1 0 0 1 0 0 0 0 0 1## 6 1 0 0 0 0 0 1 0 0 1## 7 0 1 0 0 0 1 0 1 0 0## 8 0 0 1 0 0 0 1 0 1 0## 9 0 0 0 0 0 0 0 1 0 1## 10 0 0 0 0 1 1 0 0 1 0
Edge List
Each row = 1 edge between node X and node Y
| V1 | V2 |
|---|---|
| 1 | 2 |
| 1 | 6 |
| 1 | 5 |
| 1 | 15 |
| 1 | 21 |
| 2 | 14 |
| 2 | 7 |
| 2 | 22 |
| 3 | 4 |
| 3 | 8 |
The Mental Lexicon as a Network
The mental lexicon is generally accepted as the set of words and concepts known to an individual that is stored in that person's long-term memory.
Semantic memory is the part of long-term memory that stores general facts and information about the world.
There is a lot of structure within these systems! Linguistic units are not independent of each other, and have complex, varied relationships with each other.
The Building Blocks of Language Networks
What counts as a node?
- phonemes, letters, words, syllables, morphemes, sentences
- levels of analysis in psycholinguistics
- needs to be consistently implemented across the same network
What counts as an edge?
- usually depicts similarity or overlap in features or association between words (a meaningful relation between linguistic units)
- ideally theoretically driven (but could be exploratory as well)
- what is a meaningful relationship to model?
- what is the question you want to ask of the network?
Language network structure affects processing
Semantic network
Well-connected words in the semantic network are better learned, recalled, and retrieved than words that are less well-connected.
- this holds even after taking word frequency into account
Mak, M. H., & Twitchell, H. (2020). Evidence for preferential attachment: Words that are more well connected in semantic networks are better at acquiring new links in paired-associate learning. Psychonomic Bulletin & Review, 27(5), 1059-1069. De Deyne, S., Navarro, D. J., Perfors, A., Brysbaert, M., & Storms, G. (2019). The “Small World of Words” English word association norms for over 12,000 cue words. Behavior Research Methods, 51(3), 987-1006.
Language network structure affects processing
Phonological network
Words with higher clustering coefficients are more slowly recognized than words with lower clustering coefficients in spoken word recognition tasks.
- even though the number of phonological neighbors is the same
Chan, K. Y., & Vitevitch, M. S. (2009). The influence of the phonological neighborhood clustering coefficient on spoken word recognition. Journal of Experimental Psychology: Human Perception and Performance, 35(6), 1934-1949. Chan, K. Y., & Vitevitch, M. S. (2010). Network structure influences speech production. Cognitive Science, 34(4), 685-697.