Graphs and Networks
0 likes281 views
The document discusses graphs and networks. It provides an overview of topics related to networks including big data, social networks, contagion, degree distribution and spectral graph theory. It discusses types of networks like social networks and where they are applied. It also discusses concepts like centrality, clustering, and dynamics of networks changing over time. Finally, it discusses potential applications and ideas like using networks to model epidemiology and detect abnormal behaviors.
Graphs and Networks
- 1. Graphs and networks Francisco Restivo fjr@fe.up.pt slideshare.net/frestivo
- 2. Topics The explosion of Big Data Social Networks Contagion Degree distribution Spectral Graph 2SSIIM, 2020/10/21
- 3. About me 3SSIIM, 2020/10/21 Lic. EE (6 anos) D.Phil. Prof. Assoc. Director Prof. Assoc Signals DSP Multiprocessor systems Biomedical Systems Complex systems Manufacturing systems Multi-agent systems Social systems Networks Lic. EE (6 anos) D.Phil. Prof. Assoc. Director Prof. AssocLic. EE (6 anos) D.Phil. Prof. Assoc. Director Prof. Assoc
- 5. 5SSIIM, 2020/10/21 Social media timeline https://www.future-marketing.co.uk/the-history-of-social-media/
- 7. Networks Networks are everywhere Social, biological, financial, etc Complex networks Communities Contagion Controversies Society! 7SSIIM, 2020/10/21
- 8. Social networks Like, comment, share, cite Dating e-Commerce Payments Digital marketing Political marketing Fraud, crime 8SSIIM, 2020/10/21
- 9. Where are we? Complex networks Actors influencing and being influenced by other actors But humans are not software agents Difficult to establish consensus Intelligence highly needed Maybe biology could inspire us... SSIIM, 2020/10/21 9
- 10. RIPON Voter Engagement Platform SSIIM, 2020/10/21 10
- 13. SO?! SSIIM, 2020/10/21 13 Let's have a look at networks and graphs
- 14. SSIIM, 2020/10/21 14 Euler 1707 - 1783
- 15. Basics of graphs and networks G = (V, E) O(G) = |V| order S(G) = |E| size A adjacency matrix Ki degree of vertex i Directed/undirected SSIIM, 2020/10/21 15
- 16. SSIIM, 2020/10/21 16 Relations | Matrices | Graphs 16 A = {Braga, Porto, Lisboa, Madrid, Barcelona, Paris} R A x A Braga Porto Lisboa Madrid Barcelona Paris Braga 0 1 0 0 0 0 Porto 1 0 1 0 0 0 Lisboa 0 1 0 1 0 0 Madrid 0 0 1 0 1 1 Barcelona 0 0 0 1 0 1 Paris 0 0 0 1 1 0 Cidade Cidade Braga Porto Porto Lisboa Lisboa Madrid Madrid Barcelona Madrid Paris Barcelona Paris
- 17. SSIIM, 2020/10/21 17 Composition of relations Br Po Li Ma Ba Pa Br Po Li Ma Ba Pa Br Po Li Ma Ba Pa Br 0 1 0 0 0 0 x Br 0 1 0 0 0 0 = Br 1 0 1 0 0 0 Po 1 0 1 0 0 0 Po 1 0 1 0 0 0 Po 0 2 0 1 0 0 Li 0 1 0 1 0 0 Li 0 1 0 1 0 0 Li 1 0 2 0 1 1 Ma 0 0 1 0 1 1 Ma 0 0 1 0 1 1 Ma 0 1 0 3 1 1 Ba 0 0 0 1 0 1 Ba 0 0 0 1 0 1 Ba 0 0 1 1 2 1 Pa 0 0 0 1 1 0 Pa 0 0 0 1 1 0 Pa 0 0 1 1 1 2 RxR (distance 2) Why? And RxRxR?
- 18. SSIIM, 2020/10/21 18 Reflexive: xRx Symmetric: if xRy then yRx Transitive: if xRy e yRz then xRz Anti-symmetric: if xRy and yRx then x=y Total order: (x,y) xRy or yRx Properties of relations
- 19. SSIIM, 2020/10/21 19 Equivalence relation Reflexive Symmetric Transitive Equivalence classes e.g. relation 'being sit at the same table'
- 20. SSIIM, 2020/10/21 20 Partial | total order Reflexive Transitive Anti-symmetric (Total order) Order | ranking Hasse diagram e.g. relation x divides y, A = {1, 2 10}
- 21. SSIIM, 2020/10/21 21 Matrix multiplication 1/2 There is an adjacency matrix associated to every relation Relation: x is child of y Manuel Ant坦nio Jo達o Pedro Joaquim Francisco Manuel 0 0 0 0 0 0 Ant坦nio 1 0 0 0 0 0 Jo達o 1 0 0 0 0 0 Pedro 0 1 0 0 0 0 Joaquim 0 0 1 0 0 0 Francisco 0 0 1 0 0 0
- 22. SSIIM, 2020/10/21 22 Matrix multiplication 2/2 Composition of relations: x is child of y AND y is child of z x is grandchild of z RxR: Manuel Ant坦nio Jo達o Pedro Joaquim Francisco Manuel 0 0 0 0 0 0 Ant坦nio 0 0 0 0 0 0 Jo達o 0 0 0 0 0 0 Pedro 1 0 0 0 0 0 Joaquim 1 0 0 0 0 0 Francisco 1 0 0 0 0 0
- 24. SSIIM, 2020/10/21 24 Eigenvalues and eigenvectors
- 25. Usually not transitive (a likes b and b likes c but ...) Equivalence relations No equivalence classes But communities, clusters, etc Order relations (partial, total) No Hasse diagrams Rankings, proeminence indexes, etc SSIIM, 2020/10/21 25 Real life relations
- 26. Global metrics Number of vertexes 5 Number of edges 11 Number of components 1 Diameter 2 Density 0.55 Degree distribution SSIIM, 2020/10/21 26
- 27. Node metrics Centrality Degree: Edges per node (In/Out) Closeness: Distance to every other node Betweenness: How many shortest paths go through the node/edge PageRank | eigenvector Random walk | quality of edges 27SSIIM, 2020/10/21
- 28. Common problems Distances, paths, shortest paths Measuring importance Centrality, prestige, influence (incoming links) Diffusion modeling Ideas, epidemiological Clustering Leiden, Girvan-Newman, Chinese whisper 28SSIIM, 2020/10/21
- 29. Dynamics Networks may have a temporal dimension Interactions follow, like, share, mention, retweet, hashtag, etc occur in sequence Network nodes, edges - properties evolve in time SSIIM, 2020/10/21 29
- 30. Network footprints Degree distribution Spectral graph theory (very hard topic) Spectrum: the set of eigenvalues Spectral clustering SSIIM, 2020/10/21 30
- 47. Epidemiology Learn to formulate problems in a way that computers can solve them Epidemiological models There is more than R0 and Rt https://github.com/DataForScience/Epidemiology101 Propose a gadget to trace contagion 100% anonimously... SSIIM, 2020/10/21 47
- 48. More ideas Find and use APIs Graph databases | Neo4j | Cypher Visualize citation networks Hashtag co-occurrence (Twitter, Tumblr) Detect fake/abnormal behaviours Use your imagination! SSIIM, 2020/10/21 48
- 49. Thank you! SSIIM, 2020/10/21 49