การทำเหมืองกราฟและเครือข่าย
กราฟ (Graphs) กำหนดคลาสกลไกที่เป็นทั่วไปมากกว่าชุด (Sets), ลำดับ (Sequences), จाल (Lattices), และต้นไม้ (Trees) มีช่วงกว้างของแอปพลิเคชันกราฟบนอินเทอร์เน็ตและในเครือข่ายสังคม, เครือข่ายข้อมูล, เว็บชีวภาพ, ชีวสารสนเทศศาสตร์, เคมีสารสนเทศศาสตร์, คอมพิวเตอร์วิชัน, และการดึงข้อมูลมัลติมีเดียและเนื้อหา แอปพลิเคชันของการทำเหมืองกราฟและเครือข่ายมีดังนี้:
1. การทำเหมืองรูปแบบกราฟ (Graph Pattern Mining)
คือการทำเหมืองซับกราฟบ่อย (Frequent Subgraphs) ในกราฟหนึ่งหรือชุดของกราฟ มีหลายแนวทางสำหรับการทำเหมืองรูปแบบกราฟ สามารถจัดกลุ่มเป็น แบบอิง Apriori (Apriori-based) และ แบบเติบโตรูปแบบ (Pattern Growth-based) สามารถทำเหมืองชุดของกราฟปิด (Closed Graphs) โดยกราฟ g เป็นกราฟปิด หากไม่มีซูเปอร์กราฟ g' ใดๆ ที่ให้จำนวนการสนับสนุน (Support Count) เท่ากับ g นอกจากนี้ยังมีรูปแบบกราฟแปลกประหลาดหลายแบบ เช่น กราฟบ่อยประมาณ (Approximate Frequent Graphs), กราฟสอดคล้อง (Coherent Graphs), และ กราฟหนาแน่น (Dense Graphs) ข้อจำกัดที่ผู้ใช้กำหนด (User-defined Constraints) สามารถขับเคลื่อนลึกเข้าไปในขั้นตอนการทำเหมืองรูปแบบกราฟเพื่อเพิ่มประสิทธิภาพการทำเหมือง
2. การสร้างแบบจำลองทางสถิติของเครือข่าย (Statistical Modeling of Networks)
เครือข่ายประกอบด้วยชุดของโหนด (Nodes) แต่ละตัวเทียบเท่ากับวัตถุที่เกี่ยวข้องกับชุดคุณสมบัติ และชุดของเส้นขอบ (Edges/Links) เชื่อมโหนดเหล่านั้น อธิบายความสัมพันธ์ระหว่างวัตถุ
- เครือข่ายแบบสม่ำเสมอ (Homogeneous Network): หากโหนดและลิงก์บางส่วนเป็นของประเภทเดียวกัน เช่น เครือข่ายเพื่อน, เครือข่ายผู้ร่วมเขียน, หรือเครือข่ายหน้าเว็บอินเทอร์เน็ต
- เครือข่ายแบบหลากหลาย (Heterogeneous Network): หากโหนดและการเชื่อมต่อเป็นของประเภทต่างกัน เช่น เครือข่ายการเผยแพร่ (Publication Networks - เชื่อมต่อผู้เขียน, การประชุม, บทความ, ข้อความ) และ เครือข่ายดูแลสุขภาพ (Health-care Networks - เชื่อมต่อหมอ, พยาบาล, ผู้ป่วย, โรค, การรักษา)
3. การทำความสะอาด, บูรณาการ, และตรวจสอบข้อมูลด้วยการวิเคราะห์เครือข่ายข้อมูล (Data Cleaning, Integration, and Validation by Information Network Analysis)
ความซ้ำซ้อนของข้อมูล (Information Redundancy) อาจมีอยู่ระหว่างองค์ประกอบต่างๆ ของข้อมูลที่เชื่อมโยงกันในเครือข่ายขนาดใหญ่ ความซ้ำซ้อนของข้อมูลสามารถวิเคราะห์ในเครือข่ายดังกล่าวเพื่อดำเนินการทำความสะอาดข้อมูลคุณภาพ, บูรณาการข้อมูล, ตรวจสอบข้อมูล, และการค้นหาความน่าเชื่อถือ (Trustability Search) โดยการวิเคราะห์เครือข่าย
4. การจัดกลุ่มและจัดประเภทของกราฟและเครือข่ายสม่ำเสมอ (Clustering and Classification of Graphs and Homogeneous Networks)
วิธีการวิเคราะห์กลุ่มได้รับการพัฒนาบนเครือข่ายขนาดใหญ่เพื่อเปิดเผยกลไกเครือข่าย ค้นพบชุมชนที่ซ่อนอยู่, ฮับ (Hubs), และค่าผิดปกติ (Outliers) ขึ้นอยู่กับกลไกทोपอลอจีของเครือข่ายและคุณสมบัติที่เกี่ยวข้อง มีหลายประเภทของวิธีจัดกลุ่มเครือข่ายที่พัฒนาขึ้น และสามารถจัดกลุ่มเป็น อัลกอริทึมแบบแบ่งพาร์ติชัน (Partitioning), แบบลำดับชั้น (Hierarchical), หรือ แบบอิงความหนาแน่น (Density-based)
5. การจัดกลุ่ม, การจัดอันดับ, และการจัดประเภทของเครือข่ายหลากหลาย (Clustering, Ranking, and Classification of Heterogeneous Networks)
เครือข่ายหลากหลายประกอบด้วยโหนดและการเชื่อมต่อที่เชื่อมโยงกันของหลายประเภท กลไกเชื่อมโยงเช่นนี้มีข้อมูลสมบูรณ์ ซึ่งสามารถนำไปใช้เพื่อปรับปรุงโหนดและลิงก์ร่วมกัน และเผยแพร่การสังเกตจากประเภทหนึ่งไปยังอีกประเภทหนึ่ง การจัดกลุ่มและจัดอันดับของเครือข่ายหลากหลายดังกล่าวสามารถดำเนินการได้อย่างใกล้ชิด เพราะโหนดที่มีอันดับสูงในกลุ่มสามารถมีส่วนร่วมมากกว่าคู่คู่ที่มีอันดับต่ำในการคำนวณความ凝聚力 (Cohesiveness) ของกลุ่ม
