ในการศึกษาเครือข่ายที่ซับซ้อนเครือข่ายจะถูกกล่าวว่ามีโครงสร้างชุมชนก็ต่อเมื่อโหนดของเครือข่ายสามารถจัดกลุ่มได้อย่างง่ายดายเป็นชุดของโหนด (ซึ่งอาจทับซ้อนกันได้) โดยที่แต่ละชุดของโหนดมีการเชื่อมต่อกันอย่างหนาแน่นภายใน ในกรณีเฉพาะของ การค้นหาชุมชน ที่ไม่ทับซ้อนกันหมายความว่าเครือข่ายจะแบ่งออกเป็นกลุ่มของโหนดที่มีการเชื่อมต่อกันอย่างหนาแน่นภายในและมีการเชื่อมต่อที่เบาบางกว่าระหว่างกลุ่ม แต่ ก็อนุญาตให้มีชุมชน ที่ทับซ้อนกัน ได้ เช่นกัน คำจำกัดความทั่วไปนั้นอิงตามหลักการที่ว่าคู่ของโหนดมีแนวโน้มที่จะเชื่อมต่อกันมากขึ้นหากทั้งสองเป็นสมาชิกของชุมชนเดียวกัน และมีแนวโน้มที่จะเชื่อมต่อกันน้อยลงหากพวกมันไม่ได้อยู่ในชุมชนเดียวกัน ปัญหาที่เกี่ยวข้องแต่แตกต่างกันคือการค้นหาชุมชนซึ่งเป้าหมายคือการค้นหาชุมชนที่จุดยอดใดจุดหนึ่งเป็นสมาชิกอยู่

ในการศึกษาเครือข่ายเช่น เครือข่ายคอมพิวเตอร์และสารสนเทศ เครือข่ายสังคม และเครือข่ายชีวภาพ พบว่ามีลักษณะร่วมกันหลายประการ รวมถึงคุณสมบัติแบบ โลกเล็ก ( small-world property) การกระจายระดับแบบหางหนัก (heavy-tailed degree distributions ) และการรวมกลุ่ม (clustering)เป็นต้น ลักษณะร่วมกันอีกประการหนึ่งคือโครงสร้างชุมชน^{[ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ]} ในบริบทของเครือข่าย โครงสร้างชุมชนหมายถึงการเกิดขึ้นของกลุ่มโหนดในเครือข่ายที่มีการเชื่อมต่อภายในหนาแน่นกว่าการเชื่อมต่อกับส่วนที่เหลือของเครือข่าย ดังแสดงในภาพตัวอย่างทางด้านขวา ความไม่สม่ำเสมอของการเชื่อมต่อนี้บ่งชี้ว่าเครือข่ายมีการแบ่งแยกตามธรรมชาติบางอย่างภายใน

โดยทั่วไปแล้ว ชุมชนมักถูกนิยามโดยการแบ่งกลุ่มของเซตของจุดยอด กล่าวคือ แต่ละจุดยอดจะถูกจัดอยู่ในชุมชนเดียวเท่านั้น ดังแสดงในภาพ นี่เป็นการทำให้ง่ายขึ้นอย่างมีประโยชน์ และวิธีการตรวจจับชุมชนส่วนใหญ่จะพบโครงสร้างชุมชนประเภทนี้ อย่างไรก็ตาม ในบางกรณี การแสดงผลที่ดีกว่าอาจเป็นการที่จุดยอดอยู่ในหลายชุมชน เช่น อาจเกิดขึ้นในเครือข่ายสังคมออนไลน์ที่แต่ละจุดยอดแทนบุคคล และชุมชนแทนกลุ่มเพื่อนที่แตกต่างกัน เช่น ชุมชนหนึ่งสำหรับครอบครัว ชุมชนหนึ่งสำหรับเพื่อนร่วมงาน ชุมชนหนึ่งสำหรับเพื่อนในชมรมกีฬาเดียวกัน เป็นต้น การใช้กลุ่มย่อย (cliques) ในการตรวจจับชุมชนที่กล่าวถึงด้านล่างนี้เป็นเพียงตัวอย่างหนึ่งของวิธีการค้นหาโครงสร้างชุมชนที่ทับซ้อนกันเช่นนี้

เครือข่ายบางเครือข่ายอาจไม่มีโครงสร้างชุมชนที่มีความหมายใดๆ ตัวอย่างเช่น แบบจำลองเครือข่ายพื้นฐานหลายแบบ เช่นกราฟสุ่มและแบบจำลองบาราบาซี-อัลเบิร์ตไม่แสดงโครงสร้างชุมชน

โครงสร้างชุมชนค่อนข้างพบได้ทั่วไปในเครือข่ายจริง เครือข่ายสังคมประกอบด้วยกลุ่มชุมชน (ซึ่งเป็นที่มาของคำนี้) โดยอิงตามสถานที่ตั้ง ความสนใจ อาชีพ ฯลฯ ที่เหมือนกัน^{[ 5 ] [ 6 ]}

การค้นหาโครงสร้างชุมชนพื้นฐานในเครือข่าย หากมีอยู่จริง มีความสำคัญด้วยเหตุผลหลายประการ ชุมชนช่วยให้เราสร้างแผนที่ขนาดใหญ่ของเครือข่ายได้ เนื่องจากชุมชนแต่ละแห่งทำหน้าที่เหมือนโหนดเมตาในเครือข่าย ซึ่งทำให้การศึกษาเครือข่ายง่ายขึ้น^{[ 7 ]}

ชุมชนแต่ละแห่งยังช่วยให้เข้าใจถึงการทำงานของระบบที่แสดงโดยเครือข่ายได้ดียิ่งขึ้น เนื่องจากชุมชนมักจะสอดคล้องกับหน่วยการทำงานของระบบ ในเครือข่ายเมตาบอลิซึม กลุ่มการทำงานดังกล่าวจะสอดคล้องกับวัฏจักรหรือวิถี ในขณะที่ในเครือข่ายปฏิสัมพันธ์ของโปรตีนชุมชนจะสอดคล้องกับโปรตีนที่มีฟังก์ชันการทำงานที่คล้ายคลึงกันภายในเซลล์ชีวภาพ ในทำนองเดียวกัน เครือข่ายการอ้างอิงจะสร้างชุมชนตามหัวข้อการวิจัย^{[ 1 ] การสามารถระบุโครงสร้างย่อยเหล่านี้ภายในเครือข่ายจะช่วยให้เข้าใจว่าการทำงานและโทโพโลยีของเครือข่ายส่งผลกระทบต่อกันอย่างไร ข้อมูลเชิงลึกดังกล่าวอาจเป็นประโยชน์ในการ ปรับปรุง}อัลกอริธึมบางอย่างบนกราฟ เช่นการจัดกลุ่มสเปกตรัม [ ^{8 ]}

ที่สำคัญ ชุมชนมักมีคุณสมบัติที่แตกต่างจากคุณสมบัติโดยเฉลี่ยของเครือข่ายมาก ดังนั้น การมุ่งเน้นเฉพาะคุณสมบัติโดยเฉลี่ยจึงมักพลาดคุณสมบัติที่สำคัญและน่าสนใจหลายอย่างภายในเครือข่าย ตัวอย่างเช่น ในเครือข่ายสังคมหนึ่งๆ อาจมีกลุ่มที่ชอบเข้าสังคมและกลุ่มที่ชอบเก็บตัวอยู่พร้อมกัน^{[ 7 ]}

การมีอยู่ของชุมชนโดยทั่วไปส่งผลกระทบต่อกระบวนการต่างๆ เช่น การแพร่กระจายข่าวลือหรือการแพร่ระบาดของโรคที่เกิดขึ้นในเครือข่าย ดังนั้น เพื่อให้เข้าใจกระบวนการเหล่านี้อย่างถูกต้อง จึงเป็นสิ่งสำคัญที่จะต้องตรวจจับชุมชนและศึกษาว่าชุมชนเหล่านั้นส่งผลต่อกระบวนการแพร่กระจายในบริบทต่างๆ อย่างไร

สุดท้ายนี้ การประยุกต์ใช้ที่สำคัญอย่างหนึ่งของการตรวจจับชุมชนในวิทยาศาสตร์เครือข่ายคือการทำนายลิงก์ที่หายไปและการระบุลิงก์ปลอมในเครือข่าย ในระหว่างกระบวนการวัด ลิงก์บางส่วนอาจไม่ได้รับการสังเกตด้วยเหตุผลหลายประการ ในทำนองเดียวกัน ลิงก์บางส่วนอาจเข้าสู่ข้อมูลโดยไม่ถูกต้องเนื่องจากข้อผิดพลาดในการวัด ทั้งสองกรณีนี้ได้รับการจัดการอย่างดีโดยอัลกอริทึมการตรวจจับชุมชน เนื่องจากช่วยให้สามารถกำหนดความน่าจะเป็นของการมีอยู่ของขอบระหว่างโหนดคู่หนึ่งที่กำหนดได้^{[ 9 ]}

การค้นหาชุมชนภายในเครือข่ายที่กำหนดขึ้นเองอาจเป็น งานที่ต้อง ใช้การคำนวณมาก จำนวนชุมชน (ถ้ามี) ภายในเครือข่ายมักจะไม่เป็นที่ทราบ และชุมชนมักจะมีขนาดและ/หรือความหนาแน่นไม่เท่ากัน อย่างไรก็ตาม แม้จะมีปัญหาเหล่านี้ แต่ก็มีการพัฒนาและนำวิธีการค้นหาชุมชนหลายวิธีมาใช้ โดยมีระดับความสำเร็จที่แตกต่างกัน^{[ 4 ]}

หนึ่งในอัลกอริทึมที่เก่าแก่ที่สุดสำหรับการแบ่งเครือข่ายออกเป็นส่วนๆ คือ วิธี การตัดขั้นต่ำ (และรูปแบบต่างๆ เช่น การตัดตามอัตราส่วน และการตัดแบบปรับมาตรฐาน) วิธีนี้ถูกนำไปใช้ เช่น ในการปรับสมดุลภาระงานสำหรับการประมวลผลแบบขนานเพื่อลดการสื่อสารระหว่างโหนดโปรเซสเซอร์ให้น้อยที่สุด

ในวิธีการตัดขั้นต่ำ เครือข่ายจะถูกแบ่งออกเป็นจำนวนส่วนที่กำหนดไว้ล่วงหน้า ซึ่งโดยปกติจะมีขนาดใกล้เคียงกัน โดยเลือกให้จำนวนขอบระหว่างกลุ่มมีน้อยที่สุด วิธีนี้ใช้ได้ผลดีในแอปพลิเคชันหลายอย่างที่ตั้งใจไว้แต่แรก แต่ไม่เหมาะสมนักสำหรับการค้นหาโครงสร้างชุมชนในเครือข่ายทั่วไป เนื่องจากจะพบชุมชนโดยไม่คำนึงว่าชุมชนเหล่านั้นจะแฝงอยู่ในโครงสร้างหรือไม่ และจะพบเพียงจำนวนคงที่เท่านั้น^{[ 10 ]}

อีกวิธีหนึ่งในการค้นหาโครงสร้างชุมชนในเครือข่ายคือ การจัดกลุ่ม แบบลำดับชั้น (Hierarchical Clustering ) ในวิธีนี้ เราจะกำหนดมาตรวัดความคล้ายคลึงที่วัดปริมาณความคล้ายคลึงบางประเภท (โดยปกติจะเป็นความคล้ายคลึงทางด้านโครงสร้าง) ระหว่างคู่ของโหนด มาตรวัดที่ใช้กันทั่วไป ได้แก่ความคล้ายคลึงแบบโคไซน์ (Cosine Similarity ) ดัชนีจาคาร์ด (Jaccard Index ) และระยะทางแฮมมิง (Hamming Distance)ระหว่างแถวของเมทริกซ์ความประชิด (Adjacency Matrix ) จากนั้นเราจะจัดกลุ่มโหนดที่คล้ายคลึงกันเข้าเป็นชุมชนตามมาตรวัดนี้ มีวิธีการจัดกลุ่มหลายแบบที่ใช้กันทั่วไป โดยสองวิธีที่ง่ายที่สุดคือ การจัดกลุ่มแบบเชื่อมโยงเดี่ยว (Single-Linkage Clustering ) ซึ่งสองกลุ่มจะถือว่าเป็นชุมชนที่แยกจากกันก็ต่อเมื่อคู่ของโหนดทั้งหมดในกลุ่มที่แตกต่างกันมีความคล้ายคลึงต่ำกว่าเกณฑ์ที่กำหนด และการจัดกลุ่มแบบเชื่อมโยงสมบูรณ์ (Complete Linkage Clustering ) ซึ่งโหนดทั้งหมดภายในทุกกลุ่มมีความคล้ายคลึงมากกว่าเกณฑ์ที่กำหนด ขั้นตอนสำคัญคือวิธีการกำหนดค่าเกณฑ์ที่จะหยุดการจัดกลุ่มแบบรวมกลุ่ม ซึ่งบ่งชี้ถึงโครงสร้างชุมชนที่ใกล้เคียงกับค่าที่เหมาะสมที่สุด กลยุทธ์ทั่วไปคือการสร้างตัวชี้วัดหนึ่งตัวหรือหลายตัวที่ตรวจสอบคุณสมบัติโดยรวมของเครือข่าย ซึ่งจะมีค่าสูงสุดในขั้นตอนการจัดกลุ่มที่กำหนด แนวทางที่น่าสนใจในทิศทางนี้คือการใช้มาตรวัดความคล้ายคลึงหรือความแตกต่างต่างๆ ที่รวมกันผ่านผลรวมนูน [ ^{11 ] การ}ประมาณค่าอีกวิธีหนึ่งคือการคำนวณปริมาณที่ตรวจสอบความหนาแน่นของขอบภายในคลัสเตอร์โดยสัมพันธ์กับความหนาแน่นระหว่างคลัสเตอร์ เช่น ความหนาแน่นของการแบ่งกลุ่ม ซึ่งได้รับการเสนอเมื่อมีการกำหนดเมตริกความคล้ายคลึงระหว่างขอบ (ซึ่งอนุญาตให้กำหนดชุมชนที่ทับซ้อนกันได้) ^{[ 12 ]}และขยายเมื่อมีการกำหนดความคล้ายคลึงระหว่างโหนด ซึ่งช่วยให้สามารถพิจารณาคำจำกัดความทางเลือกของชุมชน เช่น กลุ่ม (เช่น กลุ่มของโหนดที่มีจำนวนลิงก์ที่คล้ายกันเมื่อเทียบกับเพื่อนบ้านเดียวกัน แต่ไม่จำเป็นต้องเชื่อมต่อกันเอง) ^{[ 13 ]}วิธีการเหล่านี้สามารถขยายเพื่อพิจารณาเครือข่ายหลายมิติได้ เช่น เมื่อเรากำลังจัดการกับเครือข่ายที่มีโหนดที่มีลิงก์ประเภทต่างๆ กัน^{[ 13 ]}

อัลกอริทึมที่ใช้กันทั่วไปอีกตัวหนึ่งสำหรับการค้นหาชุมชนคือ อัลกอริ ทึมGirvan–Newman ^{[ 1 ]} อัลกอริทึมนี้จะระบุขอบในเครือข่ายที่อยู่ระหว่างชุมชน จากนั้นจึงลบขอบเหล่านั้นออก เหลือไว้เพียงชุมชนเท่านั้น การระบุจะทำโดยใช้การวัดความสำคัญระหว่างกลาง ตามทฤษฎีกราฟ ซึ่งกำหนดตัวเลขให้กับแต่ละขอบ โดยตัวเลขจะมีค่ามากหากขอบนั้นอยู่ "ระหว่าง" โหนดหลายคู่

อัลกอริทึม Girvan–Newman ให้ผลลัพธ์ที่มีคุณภาพสมเหตุสมผลและเป็นที่นิยมเนื่องจากมีการนำไปใช้ในซอฟต์แวร์มาตรฐานหลายแพ็กเกจ แต่ก็ทำงานช้าเช่นกัน โดยใช้เวลา O( m²n )บนเครือข่ายที่ มีจุดยอด nจุดและ ขอบ mเส้น ทำให้ไม่สามารถใช้งานได้จริงสำหรับเครือข่ายที่มีโหนดมากกว่าสองสามพัน^{โหนด[ 14 ]}

แม้จะมีข้อเสียที่ทราบกันดีอยู่แล้ว แต่วิธีการตรวจจับชุมชนที่ใช้กันอย่างแพร่หลายวิธีหนึ่งคือการเพิ่มค่าโมดูลาร์ให้สูงสุด^{[ 14 ]}โมดูลาร์ลิตี้เป็นฟังก์ชันผลประโยชน์ที่วัดคุณภาพของการแบ่งเครือข่ายออกเป็นชุมชน วิธีการเพิ่มค่าโมดูลาร์ให้สูงสุดจะตรวจจับชุมชนโดยการค้นหาการแบ่งเครือข่ายที่เป็นไปได้หนึ่งส่วนหรือมากกว่าที่มีค่าโมดูลาร์สูงเป็นพิเศษ เนื่องจากการค้นหาอย่างละเอียดในทุกการแบ่งที่เป็นไปได้มักทำได้ยาก อัลกอริทึมที่ใช้งานได้จริงจึงใช้พื้นฐานจากวิธีการเพิ่มประสิทธิภาพโดยประมาณ เช่น อัลกอริทึมแบบโลภ (greedy algorithms) การจำลองการอบอ่อน (simulated annealing) หรือการเพิ่มประสิทธิภาพเชิงสเปกตรัม (spectral optimization) โดยวิธีการต่างๆ จะให้ความสมดุลระหว่างความเร็วและความแม่นยำที่แตกต่างกัน^{[ 15 ] [ 16 ]} วิธีการเพิ่มค่าโมดูลาร์ให้สูงสุดที่เป็นที่นิยมคือวิธี Louvainซึ่งจะเพิ่มประสิทธิภาพชุมชนท้องถิ่นแบบวนซ้ำจนกว่าค่าโมดูลาร์โดยรวมจะไม่สามารถปรับปรุงได้อีกต่อไปเมื่อมีการเปลี่ยนแปลงสถานะของชุมชนในปัจจุบัน^{[ 17 ] [ 18 ]}

ประโยชน์ของการเพิ่มประสิทธิภาพโมดูลาร์นั้นเป็นที่น่าสงสัย เนื่องจากมีการแสดงให้เห็นแล้วว่าการเพิ่มประสิทธิภาพโมดูลาร์มักจะไม่สามารถตรวจจับคลัสเตอร์ที่มีขนาดเล็กกว่าระดับหนึ่งได้ ขึ้นอยู่กับขนาดของเครือข่าย ( ขีดจำกัดความละเอียด^{[ 19 ]} ) ในทางกลับกัน ภูมิทัศน์ของค่าโมดูลาร์นั้นมีลักษณะเฉพาะด้วยความเสื่อมโทรมอย่างมากของพาร์ติชันที่มีโมดูลาร์สูง ใกล้เคียงกับค่าสูงสุดสัมบูรณ์ ซึ่งอาจแตกต่างกันมาก^{[ 20 ]}

วิธีการที่อิงตามการอนุมานทางสถิติพยายามที่จะปรับแบบจำลองเชิงกำเนิดให้เข้ากับข้อมูลเครือข่าย ซึ่งเข้ารหัสโครงสร้างชุมชน ข้อได้เปรียบโดยรวมของแนวทางนี้เมื่อเทียบกับทางเลือกอื่นคือลักษณะที่เป็นหลักการมากกว่า และความสามารถในการจัดการกับประเด็นสำคัญทางสถิติ โดย เนื้อแท้ วิธีการส่วนใหญ่ในวรรณกรรมนั้นอิงตามแบบจำลองบล็อกสุ่ม^{[ 21 ]}เช่นเดียวกับรูปแบบต่างๆ รวมถึงการเป็นสมาชิกแบบผสม^{[ 22 ] [ 23 ]} การแก้ไขระดับ^{[ 24 ]}และโครงสร้างแบบลำดับชั้น^{[ 25 ]}การเลือกแบบจำลองสามารถทำได้โดยใช้แนวทางที่เป็นหลักการ เช่นความยาวคำอธิบายขั้นต่ำ^{[ 26 ] [ 27 ]} (หรือเทียบเท่ากับการเลือกแบบจำลองแบบเบย์เซียน^{[ 28 ]} ) และ การ ทดสอบอัตราส่วนความน่าจะเป็น^{[ 29 ]}ปัจจุบันมีอัลกอริทึมมากมายที่ใช้ในการอนุมานแบบจำลองบล็อกสุ่มอย่างมีประสิทธิภาพ รวมถึงการแพร่กระจายความเชื่อ^{[ 30 ] [ 31 ]} และมอนเตคาร์โลแบบ รวมกลุ่ม ^{[ 32 ]}

ตรงกันข้ามกับแนวทางที่พยายามจัดกลุ่มเครือข่ายโดยพิจารณาจากฟังก์ชันวัตถุประสงค์ วิธีการประเภทนี้จะอิงตามแบบจำลองเชิงกำเนิด ซึ่งไม่เพียงแต่ทำหน้าที่เป็นคำอธิบายโครงสร้างขนาดใหญ่ของเครือข่ายเท่านั้น แต่ยังสามารถใช้เพื่อสรุปข้อมูลและทำนายการเกิดลิงก์ที่ขาดหายไปหรือลิงก์ปลอมในเครือข่ายได้อีก ด้วย ^{[ 33 ] [ 34 ]}

กลุ่มย่อย (Cliques)คือกราฟย่อยที่ทุกโหนดเชื่อมต่อกับทุกโหนดอื่นในกลุ่มย่อยนั้น เนื่องจากโหนดไม่สามารถเชื่อมต่อกันอย่างแน่นหนากว่านี้ได้ จึงไม่น่าแปลกใจที่มีวิธีการตรวจจับชุมชนในเครือข่ายมากมายที่อาศัยการตรวจจับกลุ่มย่อยในกราฟและการวิเคราะห์การทับซ้อนกันของกลุ่มย่อยเหล่านั้น โปรดทราบว่า เนื่องจากโหนดหนึ่งสามารถเป็นสมาชิกของกลุ่มย่อยได้มากกว่าหนึ่งกลุ่ม โหนดหนึ่งจึงสามารถเป็นสมาชิกของชุมชนได้มากกว่าหนึ่งชุมชนในวิธีการเหล่านี้ ทำให้เกิด " โครงสร้างชุมชนที่ทับซ้อนกัน "

แนวทางหนึ่งคือการค้นหา " คลิกสูงสุด " นั่นคือการค้นหาคลิกที่ไม่ใช่กราฟย่อยของคลิกอื่นใด อัลกอริทึมแบบคลาสสิกในการค้นหาสิ่งเหล่านี้คืออัลกอริทึม Bron–Kerboschการทับซ้อนของสิ่งเหล่านี้สามารถใช้เพื่อกำหนดชุมชนได้หลายวิธี วิธีที่ง่ายที่สุดคือการพิจารณาเฉพาะคลิกสูงสุดที่มีขนาดใหญ่กว่าขนาดขั้นต่ำ (จำนวนโหนด) การรวมกันของคลิกเหล่านี้จะกำหนดกราฟย่อยซึ่งส่วนประกอบ (ส่วนที่ไม่เชื่อมต่อ) จะกำหนดชุมชน^{[ 35 ]}แนวทางดังกล่าวนี้มักถูกนำไปใช้ในซอฟต์แวร์วิเคราะห์เครือข่ายสังคมเช่น UCInet

แนวทางทางเลือกคือการใช้คลิกที่มีขนาดคงที่การทับซ้อนของคลิกเหล่านี้สามารถใช้เพื่อกำหนดไฮเปอร์กราฟ แบบ ปกติหรือโครงสร้างที่เป็นการวางนัยทั่วไปของกราฟเส้น (กรณีที่) ซึ่งเรียกว่า " กราฟคลิก " ^{[ 36 ]} กราฟคลิกมีจุดยอดที่แสดงถึงคลิกในกราฟดั้งเดิม ในขณะที่ขอบของกราฟคลิกบันทึกการทับซ้อนของคลิกในกราฟดั้งเดิม การใช้วิธีการตรวจจับชุมชนก่อนหน้านี้ (ซึ่งกำหนดแต่ละโหนดให้กับชุมชน) กับกราฟคลิกจะกำหนดแต่ละคลิกให้กับชุมชน จากนั้นสามารถใช้เพื่อกำหนดการเป็นสมาชิกชุมชนของโหนดในคลิกได้ อีกครั้ง เนื่องจากโหนดอาจอยู่ในหลายคลิก จึงสามารถเป็นสมาชิกของหลายชุมชนได้ ตัวอย่างเช่น วิธีการแพร่กระจายของคลิก^{[ 37 ]}กำหนดชุมชนเป็นคลัสเตอร์การแพร่กระจายของคลิกเพื่อทำเช่นนี้ จะค้นหาคลิกทั้งหมดในเครือข่าย นั่นคือกราฟย่อยที่สมบูรณ์ทั้งหมดของโหนด จากนั้นจะกำหนดว่ากลุ่มย่อยสองกลุ่มจะอยู่ติดกันหากมีโหนดร่วมกัน ซึ่งใช้ในการกำหนดขอบในกราฟกลุ่มย่อย ชุมชนจะถูกกำหนดให้เป็นการรวมกันสูงสุดของกลุ่มย่อยต่างๆ ซึ่งเราสามารถเข้าถึงกลุ่มย่อยใดๆ จากกลุ่มย่อยอื่นๆ ได้ผ่านชุดความสัมพันธ์ของกลุ่มย่อยต่างๆ กล่าวคือ ชุมชนเป็นเพียงส่วนประกอบที่เชื่อมต่อกันในกราฟกลุ่มย่อย เนื่องจากโหนดหนึ่งสามารถอยู่ในกลุ่มการแพร่กระจายของกลุ่มย่อยต่างๆ ได้หลายกลุ่มในเวลาเดียวกัน ชุมชนจึงสามารถทับซ้อนกันได้ ${\displaystyle k}$${\displaystyle k}$${\displaystyle k=2}$${\displaystyle k}$${\displaystyle k}$${\displaystyle k}$${\displaystyle k}$${\displaystyle k-1}$${\displaystyle k}$${\displaystyle k}$${\displaystyle k}$${\displaystyle k}$${\displaystyle k}$

เครือข่ายสามารถแสดงหรือฉายลงบนพื้นที่แฝง ได้ โดยใช้ วิธี การเรียนรู้การแสดงแทนเพื่อแสดงระบบได้อย่างมีประสิทธิภาพ จากนั้นสามารถใช้วิธีการจัดกลุ่ม ต่างๆ เพื่อตรวจจับโครงสร้างชุมชน สำหรับพื้นที่ยูคลิด สามารถใช้วิธีการต่างๆ เช่น การตรวจจับชุมชน Silhouette ที่ใช้การฝังตัว ^{[ 38 ]}สำหรับพื้นที่แฝงไฮเปอร์จีโอเมตริก สามารถใช้วิธีการช่องว่างวิกฤตหรือวิธีการจัดกลุ่มตามความหนาแน่นที่ดัดแปลง วิธีการจัดกลุ่มแบบลำดับชั้น หรือวิธีการจัดกลุ่มตามการแบ่งส่วนได้^{[ 39 ]}

การประเมินอัลกอริทึมเพื่อตรวจหาว่าอัลกอริทึมใดมีประสิทธิภาพในการตรวจจับโครงสร้างชุมชนได้ดีกว่า ยังคงเป็นคำถามที่เปิดกว้างอยู่ การประเมินต้องอาศัยการวิเคราะห์เครือข่ายที่มีโครงสร้างที่ทราบแล้ว ตัวอย่างทั่วไปคือการทดสอบ "สี่กลุ่ม" ซึ่งเครือข่ายจะถูกแบ่งออกเป็นสี่กลุ่มที่มีขนาดเท่ากัน (โดยปกติแต่ละกลุ่มจะมี 32 โหนด) และความน่าจะเป็นของการเชื่อมต่อภายในและระหว่างกลุ่มจะแตกต่างกัน เพื่อสร้างโครงสร้างที่ท้าทายมากขึ้นหรือน้อยลงสำหรับอัลกอริทึมการตรวจจับ กราฟมาตรฐานดังกล่าวเป็นกรณีพิเศษของแบบจำลอง l-partition ^{[ 40 ]} ของCondonและKarpหรือโดยทั่วไปแล้วเป็น " แบบจำลองบล็อกสุ่ม " ซึ่งเป็นแบบจำลองเครือข่ายสุ่มทั่วไปที่มีโครงสร้างชุมชน มีการเสนอมาตรฐานที่ยืดหยุ่นกว่าอื่นๆ ที่อนุญาตให้ขนาดกลุ่มและการกระจายระดับที่ไม่ธรรมดาแตกต่างกัน เช่นมาตรฐาน LFR ^{[ 41 ] [ 42 ]} ซึ่งเป็นการขยายมาตรฐานสี่กลุ่มที่รวมถึงการกระจายระดับโหนดและขนาดชุมชนที่ไม่เหมือนกัน ทำให้เป็นการทดสอบวิธีการตรวจจับชุมชนที่เข้มงวดมากขึ้น^{[ 43 ] [ 44 ]}

เกณฑ์มาตรฐานที่สร้างโดยคอมพิวเตอร์ที่ใช้กันทั่วไปเริ่มต้นด้วยเครือข่ายของชุมชนที่กำหนดไว้อย่างดี จากนั้นโครงสร้างนี้จะเสื่อมลงโดยการเชื่อมต่อใหม่หรือลบลิงก์ และอัลกอริธึมจะตรวจจับพาร์ติชันดั้งเดิมได้ยากขึ้นเรื่อยๆ ในที่สุดเครือข่ายจะถึงจุดที่มันเป็นแบบสุ่มโดยพื้นฐาน เกณฑ์มาตรฐานประเภทนี้อาจเรียกว่า "แบบเปิด" ประสิทธิภาพบนเกณฑ์มาตรฐานเหล่านี้ได้รับการประเมินโดยการวัดเช่นข้อมูลร่วมกัน แบบปกติ หรือความแปรผันของข้อมูลพวกเขาเปรียบเทียบโซลูชันที่ได้รับจากอัลกอริธึม^{[ 42 ]}กับโครงสร้างชุมชนดั้งเดิม โดยประเมินความคล้ายคลึงกันของพาร์ติชันทั้งสอง

ในช่วงไม่กี่ปีที่ผ่านมา กลุ่มต่างๆ ได้ค้นพบผลลัพธ์ที่ค่อนข้างน่าประหลาดใจ ซึ่งแสดงให้เห็นว่ามีการเปลี่ยนแปลงเฟสเกิดขึ้นในปัญหาการตรวจจับชุมชน โดยแสดงให้เห็นว่าเมื่อความหนาแน่นของการเชื่อมต่อภายในชุมชนและระหว่างชุมชนมีความเท่าเทียมกันมากขึ้นเรื่อยๆ หรือทั้งสองอย่างมีขนาดเล็กลง (หรือเทียบเท่ากับโครงสร้างชุมชนที่อ่อนแอเกินไปหรือเครือข่ายที่เบาบางเกินไป) ชุมชนก็จะตรวจจับไม่ได้ ในแง่หนึ่ง ชุมชนยังคงมีอยู่ เนื่องจากความมีอยู่และไม่มีอยู่ของขอบยังคงมีความสัมพันธ์กับการเป็นสมาชิกชุมชนของจุดปลาย แต่ในทางทฤษฎีสารสนเทศแล้ว เป็นไปไม่ได้ที่จะติดป้ายกำกับโหนดได้ดีกว่าโอกาส หรือแม้แต่แยกแยะกราฟจากกราฟที่สร้างขึ้นโดยแบบจำลองว่าง เช่นแบบจำลอง Erdos–Renyiที่ไม่มีโครงสร้างชุมชน การเปลี่ยนแปลงนี้ไม่ขึ้นอยู่กับประเภทของอัลกอริทึมที่ใช้ในการตรวจจับชุมชน ซึ่งหมายความว่ามีข้อจำกัดพื้นฐานเกี่ยวกับความสามารถของเราในการตรวจจับชุมชนในเครือข่าย แม้กระทั่งด้วยการอนุมานแบบเบย์เซียนที่ดีที่สุด (กล่าวคือ โดยไม่คำนึงถึงทรัพยากรการคำนวณของเรา) ^{[ 45 ] [ 46 ] [ 47 ]}

พิจารณาแบบจำลองบล็อกสุ่ม ที่มี โหนดทั้งหมด n โหนด กลุ่มที่มีขนาดเท่ากัน และให้และเป็นความน่าจะเป็นของการเชื่อมต่อภายในและระหว่างกลุ่มตามลำดับ ถ้าเครือข่ายจะมีโครงสร้างแบบชุมชน เนื่องจากความหนาแน่นของลิงก์ภายในกลุ่มจะมากกว่าความหนาแน่นของลิงก์ระหว่างกลุ่ม ในกรณีที่เบาบางและจะแปรผันตามเพื่อให้ระดับเฉลี่ยคงที่: ${\displaystyle n}$${\displaystyle q=2}$${\displaystyle p_{\text{in}}}$${\displaystyle p_{\text{out}}}$${\displaystyle p_{\text{in}}>p_{\text{out}}}$${\displaystyle p_{\text{in}}}$${\displaystyle p_{\text{out}}}$${\displaystyle O(1/n)}$

${\displaystyle p_{\text{in}}=c_{\text{in}}/n}$และ${\displaystyle p_{\text{out}}=c_{\text{out}}/n}$

จากนั้นการตรวจจับชุมชนก็เป็นไปไม่ได้เมื่อ: ^{[ 46 ]}

${\displaystyle c_{\text{in}}-c_{\text{out}}={\sqrt {2(c_{\text{in}}+c_{\text{out}})}}}$

• เครือข่ายที่ซับซ้อน
• ลำดับชั้น
• ทฤษฎีเครือข่าย
• ทฤษฎีการซึมผ่าน

• การตรวจจับชุมชนในกราฟ – บทนำ
• มีการนำอัลกอริธึมสำหรับการตรวจจับชุมชนในกราฟไปใช้งานหรือไม่? – Stack Overflow
• อัลกอริทึมการตรวจจับชุมชนใน igraph แตกต่างกันอย่างไรบ้าง? – Stack Overflow