Lecture 6 Graph Mining
Lecture 6 Graph Mining
Background Graph Mining Networks/Graphs--exist everywhere. Food Web of Smallmouth Bass Leech Little Rock Lake (Cannibal) 1st Tropic Level Mosty Phytoplankton 2nd Trophic Level Many Zooplankton Internet Food Web The Social Stcture of Coutryside"Schod District T和出Ody2 Friendship Network Co-author networks
Internet Food Web Friendship Network Co-author networks Networks/Graphs -- exist everywhere. Background Graph Mining
Background Graph Mining Origin of Graph Theory: Seven Bridges of Konigsberg(proposed by Leonhard Euler()) --wiki The city of Konigsberg in Prussia(now Kaliningrad,Russia)was set on both sides of the Pregel River,and included two large islands which were connected to each other,or to the two mainland portions of the city,by seven bridges.The problem was to devise a walk through the city that would cross each of those bridges once and only once
Origin of Graph Theory: Seven Bridges of Königsberg (proposed by Leonhard Euler(欧拉)) The city of Königsberg in Prussia (now Kaliningrad, Russia) was set on both sides of the Pregel River, and included two large islands which were connected to each other, or to the two mainland portions of the city, by seven bridges. The problem was to devise a walk through the city that would cross each of those bridges once and only once. --wiki Background Graph Mining
Background Graph Mining Network/Graph-construct Data Instance Graph Instance Element Vertex Element's Attributes >Vertex Label Relation Between Edge Two Elements Type Of Relation Edge Label Relation between a →Hyper Edge Set of Elements Provide enormous flexibility for modeling the underlying data as they allow the modeler to decide on what the elements should be and the type of relations to be modeled
Network/Graph – construct Element Vertex Element’s Attributes Relation Between Two Elements Type Of Relation Vertex Label Edge Label Edge Data Instance Graph Instance Relation between a Set of Elements Hyper Edge Provide enormous flexibility for modeling the underlying data as they allow the modeler to decide on what the elements should be and the type of relations to be modeled Background Graph Mining
Background Graph Mining Networks/Graphs-applications in real-world? Information Maximization ·viral'marketing. Web-log ('blog')news propagation. Computer network security Email/IP traffic and anomaly detection ·Prediction The prediction of flow within networks
Networks/Graphs – applications in real-world? • Information Maximization • ‘viral’ marketing. • Web-log (‘blog’) news propagation. • Computer network security • Email/IP traffic and anomaly detection • Prediction • The prediction of flow within networks Background Graph Mining