เมทริกซ์ความใกล้เคียง m คูณ m สำหรับจุดข้อมูล m สามารถกำหนดเป็นกราฟหนาแน่นซึ่งแต่ละโหนดเชื่อมโยงกับส่วนอื่นๆ และน้ำหนักของขอบระหว่างกลุ่มของโหนดบางกลุ่มจะเป็นไปตามความใกล้ชิดแบบคู่ แม้ว่าแต่ละอ็อบเจ็กต์จะมีวิธีการบางอย่างที่เหมือนกันกับอ็อบเจกต์อื่น แต่สำหรับชุดข้อมูลส่วนใหญ่ ออบเจ็กต์จะเหมือนกันอย่างมหาศาลสำหรับออบเจ็กต์จำนวนน้อยและเหมือนกันเล็กน้อยกับออบเจ็กต์อื่นๆ ส่วนใหญ่
คุณลักษณะนี้สามารถใช้เพื่อกระจายกราฟความใกล้เคียง (เมทริกซ์) โดยการตั้งค่าความคล้ายคลึงต่ำ (ความต่างสูง) เป็น 0 ก่อนเริ่มกระบวนการจัดกลุ่มจริง การกระจัดกระจายสามารถนำไปใช้ได้ เช่น โดยการแบ่งลิงก์ทั้งหมดที่มี (ความต่าง) ที่เหมือนกัน (ความต่าง) ด้านล่าง (ด้านบน) เกณฑ์ที่กำหนดไว้ หรือโดยการรักษาเฉพาะลิงก์ไปยังจุดที่อยู่ใกล้เคียงที่สุด k วิธีนี้จะสร้างสิ่งที่เรียกว่ากราฟเพื่อนบ้านที่คุกเข่าที่สุด
ประโยชน์ของการทำให้กระจัดกระจายมีดังนี้ −
ขนาดข้อมูลลดลง − ปริมาณข้อมูลที่ต้องประมวลผลเพื่อจัดกลุ่มข้อมูลลดลงอย่างมาก Sparsification สามารถลบรายการได้มากกว่า 99% ในเมทริกซ์ความใกล้เคียง ดังนั้นขนาดของปัญหาที่สามารถจัดการได้จึงเพิ่มขึ้น
การจัดกลุ่มอาจทำงานได้ดีขึ้น − วิธีการ Sparsification จะรักษาการเชื่อมโยงไปยังเพื่อนบ้านที่ใกล้ที่สุดของวัตถุในขณะที่แบ่งการเชื่อมต่อไปยังวัตถุที่แตกต่างกันมากขึ้น นี่คือการรักษาหลักการเพื่อนบ้านที่ใกล้ที่สุดว่าเพื่อนบ้านที่ใกล้ที่สุดของอิทธิพลของวัตถุอยู่ในคลาสที่คล้ายคลึงกัน (คลัสเตอร์) เป็นวัตถุ ซึ่งจะลดผลกระทบของเสียงรบกวนและสิ่งผิดปกติ และสร้างความแตกต่างระหว่างคลัสเตอร์
สามารถใช้อัลกอริธึมการแบ่งกราฟได้ − มีการทำงานจำนวนมากในอัลกอริธึมฮิวริสติกในการค้นหาการแบ่งพาร์ติชั่นขั้นต่ำของกราฟแบบกระจาย โดยเฉพาะอย่างยิ่งในพื้นที่ของการคำนวณแบบขนานและการออกแบบวงจรรวม การกระจายตัวของกราฟความใกล้เคียงทำให้เกิดการใช้อัลกอริธึมการแบ่งพาร์ติชั่นกราฟสำหรับเฟสคลัสเตอร์ เช่น Opossum และ Chameleon จำเป็นต้องมีการแบ่งพาร์ติชั่นกราฟ
การกระจัดกระจายของกราฟความใกล้เคียงต้องถือเป็นขั้นตอนดั้งเดิมก่อนที่จะต้องใช้อัลกอริธึมการจัดกลุ่มจริง การกระจัดกระจายที่ดีที่สุดสามารถทำให้เมทริกซ์ความใกล้เคียงถูกแบ่งออกเป็นองค์ประกอบที่เชื่อมต่อกันซึ่งสัมพันธ์กับคลัสเตอร์ที่ต้องการ แต่ในทางปฏิบัติ สิ่งนี้จะปรากฏขึ้น
เป็นเพียงสำหรับแต่ละขอบในการเชื่อมต่อสองคลัสเตอร์หรือสำหรับแต่ละคลัสเตอร์ที่จะแบ่งออกเป็นคลัสเตอร์ย่อยที่ไม่ได้เชื่อมต่อหลายรายการ อันที่จริง มันสามารถเห็นได้เมื่อ Jarvis-Patrick และ SNN ใช้การจัดกลุ่มตามความหนาแน่น กราฟความใกล้เคียงแบบเบาบางจะเปลี่ยนไปเพื่อให้ได้กราฟความใกล้เคียงใหม่ กราฟความใกล้เคียงใหม่นี้สามารถกระจัดกระจายได้ อัลกอริธึมการจัดกลุ่มทำงานกับกราฟความใกล้เคียงซึ่งเป็นผลลัพธ์ของขั้นตอนการประมวลผลล่วงหน้าทั้งหมดเหล่านี้
