Introduction to Complex Networks, Basic Description IV124 Josef Spurný & Eva Výtvarová Faculty of Informatics, Masaryk University February 24, 2023 Complex systems, complex networks Complexity, complex system Complex system many units interacting with each other nontrivial interaction structure Many shared properties discrete entities connected by (binary) connections (links) emergent properties which are more then just a summation of sub-parts important properties on many scales (multi-scale systems) J. Spurný, E. Výtvarová ·Basic properties ·February 24, 2023 2 / 27 Complex systems, complex networks Examples of complex systems Natural systems biological networks: gene expression, metabolic networks,... inter-species interaction: food network Social systems social networks: friendship, communication,... science: citation network economic network: world trade Technological systems internet, electrical network, transport network J. Spurný, E. Výtvarová ·Basic properties ·February 24, 2023 3 / 27 Complex systems, complex networks Complex Network Analysis How? Data collection → Analysis + Visualization Why? Insight + Prediction J. Spurný, E. Výtvarová ·Basic properties ·February 24, 2023 4 / 27 Graphs, networks Graphs and networks Graph G = (V, E): V set of vertices E ⊆ V × V set of directed edges or E ⊆ {{a, b}; a, b ∈ V} undirected edges J. Spurný, E. Výtvarová ·Basic properties ·February 24, 2023 5 / 27 Graphs, networks Graphs and networks Weighted graph G = (V, E, w) weight function w : E → R Multigraph G = (V, E) E is a multiset J. Spurný, E. Výtvarová ·Basic properties ·February 24, 2023 6 / 27 Graphs, networks Link strength Strong links Structure Stability in time Resistant to change Short range – low prob. of new info Removal = high impact Weak links Flexibility, adaptability High rate of fluctuance Susceptible to change Long range - high prob. of new info Removal = insignificant J. Spurný, E. Výtvarová ·Basic properties ·February 24, 2023 7 / 27 Graphs, networks Optimal link ratio 20 strong : 80 weak Ensures "dynamic stability" Adaptability Flexibility Resistance to stress Ability to relax Too little weak links: rigidity, fragility Too many weak links: instability, chaotic behavior J. Spurný, E. Výtvarová ·Basic properties ·February 24, 2023 8 / 27 Graphs, networks Graphs and networks – examples World trade oriented, weighted (sum of transactions) Social networks – friendship undirected, unweighted Protein interaction undirected, unweighted, loops Organization social network undirected, weighted multigraph (multilayer network) J. Spurný, E. Výtvarová ·Basic properties ·February 24, 2023 9 / 27 Graphs, networks Terminology edge vs. link / connection vertex vs. node / agent A term graph is usually used in case of general mathematical apparatus, in models of specific systems we mostly use a term network. J. Spurný, E. Výtvarová ·Basic properties ·February 24, 2023 10 / 27 Graphs, networks Definition of a network describing a real system What are the nodes? What are the edges? more possibilities of abstraction over the same dataset depends on a specific system, available data and research questions For the same set of nodes we can create different networks frequency of email communication: cooperation network friendship network frequency of in-person meetings: epidemiology network J. Spurný, E. Výtvarová ·Basic properties ·February 24, 2023 11 / 27 Graphs, networks Network analysis – relevant questions Network structure understanding which nodes are important in the network? do the nodes form clusters (communities)? is there any regularity in the structure of connections? Study of network evolution how was the network created? How does it grow? Is there a suitable model for our network? Dynamic processes on networks how does a diffusion of information or disease evolves? what is a temporary profile of a communication between nodes? We will look into these topics in future lectures. J. Spurný, E. Výtvarová ·Basic properties ·February 24, 2023 12 / 27 Graphs, networks Data structures List of neighbors: list of neighbors for each node Adjacency matrix rows – nodes (from), columns – nodes (to) 1 equals to existence of an edge, otherwise 0 weighted graphs: an edge weight instead of 1 diagonal: loops J. Spurný, E. Výtvarová ·Basic properties ·February 24, 2023 13 / 27 Graphs, networks Adjacency matrix – example       0 1 0 1 1 1 0 1 0 0 0 1 0 1 0 1 0 1 0 1 1 0 0 1 0       J. Spurný, E. Výtvarová ·Basic properties ·February 24, 2023 14 / 27 Graphs, networks Adjacency matrix – example       0 0 0 0 1 1 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0       J. Spurný, E. Výtvarová ·Basic properties ·February 24, 2023 15 / 27 Graphs, networks Adjacency matrix – example       0 3 0 1.9 2.2 3 0 0.5 0 0 0 0.5 0 2.1 0 1.9 0 2.1 0 6.9 2.2 0 0 6.9 0       J. Spurný, E. Výtvarová ·Basic properties ·February 24, 2023 16 / 27 Case Study Zachary Karate Club Domain: Anthropology Paper: Wayne W. Zachary: An Information Flow Model for Conflict and Fission in Small Groups Background story: New instructor introduced; after some time, he proposes increased training fee Club President refuses, seeing this as his intent to make more money Both figures have their own supporters Tension escalates; the club splits into two J. Spurný, E. Výtvarová ·Basic properties ·February 24, 2023 17 / 27 Case Study Karate Club Network Links present if members interact outside karate lessons J. Spurný, E. Výtvarová ·Basic properties ·February 24, 2023 18 / 27 Case Study Karate Club Adjacency Matrix J. Spurný, E. Výtvarová ·Basic properties ·February 24, 2023 19 / 27 Case Study Karate Club Adjacency Matrix J. Spurný, E. Výtvarová ·Basic properties ·February 24, 2023 20 / 27 Case Study Gephi - Force Atlas Layout J. Spurný, E. Výtvarová ·Basic properties ·February 24, 2023 21 / 27 Case Study General observations Giant component, no submodules Unweighted, undirected, unreflexive network N = 34, L = 78 J. Spurný, E. Výtvarová ·Basic properties ·February 24, 2023 22 / 27 Case Study Karate Club - Node Degree Centrality avg. degree = 4.588 J. Spurný, E. Výtvarová ·Basic properties ·February 24, 2023 23 / 27 Case Study Karate Club - Modularity pink ≈ 53 %, green ≈ 47 % J. Spurný, E. Výtvarová ·Basic properties ·February 24, 2023 24 / 27 Case Study Available tools Matlab or R Networkx for Python Open-Source Desktop Apps: CytoScape (bioinformatics) Gephi (swiss knife) SocNetV (built-in web crawler) Specific purpose: Netlytic web-based text and network analysis of public discussion media (Reddit, Twitter, YouTube, etc. ) Many more... J. Spurný, E. Výtvarová ·Basic properties ·February 24, 2023 25 / 27 Case Study Gephi Demo J. Spurný, E. Výtvarová ·Basic properties ·February 24, 2023 26 / 27