Community detection

Community detection is a powerful technique for analysing spatial networks, offering a variety of methods to uncover meaningful structures. At its core, community detection identifies highly connected subcomponents within a graph, which can reveal important patterns and relationships. The interpretation of these communities depends on the context of the graph, allowing researchers to gain insights into the underlying dynamics of the system being studied.

In this tutorial, we’ll conduct community detection using our community_detection function in the networks submodule of MuSpAn.

# Import necessary libraries
import muspan as ms
import numpy as np

# Set random seed for reproducibility
np.random.seed(42)

# Load example domain dataset
example_domain = ms.datasets.load_example_domain('Synthetic-Points-Aggregation')

# Visualise the example domain, coloring by 'Celltype'
ms.visualise.visualise(example_domain, color_by='Celltype')

MuSpAn domain loaded successfully. Domain summary:
Domain name: Aggregation
Number of objects: 2000
Collections: ['Cell centres']
Labels: ['Celltype']
Networks: []
Distance matrices: []

(<Figure size 1000x800 with 2 Axes>, <Axes: >)

Let’s generate a network to run community detection on.

# Generate the 'Centroid Delaunay' network for the example domain
ms.networks.generate_network(
    example_domain,
    network_name='Centroid Delaunay',
    network_type='Delaunay',
    max_edge_distance=70
)

# Visualise the generated network, coloring by 'Celltype'
ms.visualise.visualise_network(
    example_domain,
    network_name='Centroid Delaunay',
    visualise_kwargs=dict(color_by='Celltype', marker_size=10),
    figure_kwargs=dict(figsize=(10, 7))
)

(<Figure size 1000x700 with 3 Axes>, <Axes: >)

We perform community detection using the community_detection function in the networks submodule. Specifically, we use the Louvain community detection method, which aims to optimise modularity—ensuring there are more edges within a community than between different communities. This method has several parameters that can influence the behavior of community detection. We recommend reviewing the Louvain algorithm for a deeper understanding: https://doi.org/10.1088/1742-5468/2008/10/P10008.

In particular, the resolution parameter plays a key role in controlling the size of the detected communities. A higher resolution value tends to identify smaller, more localised communities, while a lower value results in larger, more global groupings. Adjusting this parameter allows you to tailor the community detection process to your specific needs.

Let’s see how this communtity detection method runs on our network using the default resolution parameter.

# Perform community detection using the Louvain method with a resolution of 1
communities_res_1=ms.networks.community_detection(
    example_domain,
    network_name='Centroid Delaunay',
    edge_weight_name=None,
    community_method='louvain',
    community_method_parameters=dict(resolution=1),
    community_label_name='Communities : Res = 1'
)

The community detection function adds the community labels to the objects by default and are stored under the community_label_name label name. This output can be used for futher analysis or querying.

In addition, the output of the function is a dictionary of the communities, where the keys are the community IDs which each have a list of the object ID in that community. We can see this below.

print(communities_res_1)

{0: [4, 133, 262, 134, 6, 260, 138, 20, 408, 25, 286, 164, 167, 295, 42, 427, 174, 176, 177, 49, 435, 52, 54, 55, 57, 443, 191, 323, 196, 325, 326, 451, 201, 333, 83, 339, 341, 342, 85, 218, 347, 476, 352, 353, 226, 355, 233, 364, 493, 370, 126], 1: [129, 1155, 1286, 1287, 1165, 1294, 1296, 273, 1298, 403, 1170, 1175, 1303, 1311, 1312, 1185, 163, 1187, 37, 1318, 1322, 1196, 1328, 1204, 310, 1211, 1342, 1344, 1217, 1347, 71, 1351, 330, 1226, 1359, 1234, 1235, 1109, 471, 1240, 219, 1373, 1374, 1375, 1251, 1383, 104, 1384, 1259, 1134, 1262, 1136, 1264, 1266, 1392, 1268, 1141, 1272, 1273, 1277, 1278], 2: [324, 135, 360, 431, 464, 369, 114, 111, 116, 411, 284, 189, 222], 3: [0, 385, 3, 259, 255, 263, 264, 909, 398, 15, 143, 18, 404, 1046, 407, 152, 26, 412, 927, 289, 290, 419, 293, 938, 299, 175, 434, 436, 182, 439, 956, 190, 447, 446, 194, 963, 1091, 835, 1095, 327, 456, 329, 74, 207, 208, 849, 335, 80, 469, 88, 473, 475, 482, 101, 230, 231, 105, 367, 245, 380, 253, 895], 4: [769, 770, 771, 773, 518, 777, 778, 779, 525, 526, 527, 784, 786, 788, 533, 793, 537, 539, 796, 798, 543, 545, 546, 548, 38, 554, 555, 300, 556, 562, 563, 51, 565, 564, 568, 569, 570, 575, 576, 577, 583, 587, 332, 590, 592, 594, 599, 602, 604, 605, 607, 608, 612, 613, 614, 615, 617, 624, 629, 630, 632, 377, 633, 635, 636, 643, 646, 647, 648, 650, 653, 654, 655, 657, 660, 662, 664, 409, 666, 665, 668, 672, 677, 678, 679, 683, 687, 688, 694, 697, 698, 701, 702, 192, 711, 717, 720, 722, 724, 726, 729, 738, 742, 745, 747, 749, 752, 500, 757, 502, 759, 760, 761, 762, 501, 765, 763], 5: [514, 520, 524, 781, 13, 272, 530, 277, 534, 535, 536, 279, 541, 29, 285, 550, 296, 553, 557, 303, 305, 567, 58, 572, 574, 319, 578, 581, 585, 586, 591, 606, 619, 108, 621, 623, 627, 372, 631, 638, 642, 645, 389, 137, 651, 652, 148, 663, 669, 414, 161, 676, 680, 689, 693, 442, 703, 708, 712, 714, 205, 463, 213, 474, 731, 730, 733, 478, 736, 739, 746, 240, 504, 507, 764], 6: [512, 516, 774, 519, 511, 780, 270, 528, 785, 529, 787, 531, 789, 21, 791, 538, 797, 799, 547, 549, 302, 559, 47, 560, 304, 50, 561, 566, 571, 64, 582, 584, 589, 601, 603, 96, 354, 98, 100, 611, 616, 618, 620, 625, 628, 118, 124, 637, 640, 641, 393, 149, 667, 418, 674, 682, 691, 692, 696, 700, 448, 705, 707, 710, 204, 461, 718, 719, 721, 468, 470, 732, 735, 223, 225, 489, 748, 505, 496, 753, 249, 766, 767], 7: [768, 513, 515, 772, 517, 775, 776, 521, 522, 11, 267, 523, 782, 783, 532, 790, 22, 792, 794, 795, 540, 542, 544, 551, 552, 41, 558, 56, 573, 66, 579, 580, 588, 593, 82, 338, 596, 595, 598, 597, 600, 609, 610, 622, 368, 626, 376, 639, 644, 388, 391, 649, 656, 144, 658, 659, 661, 670, 671, 673, 675, 166, 681, 171, 685, 686, 433, 690, 695, 699, 704, 706, 709, 713, 715, 716, 723, 727, 728, 734, 740, 484, 741, 743, 744, 750, 751, 754, 755, 756, 758, 503, 506, 508, 509, 510], 8: [1024, 1027, 1030, 1031, 1040, 19, 1048, 1051, 31, 1056, 1057, 1058, 1061, 1063, 1064, 1065, 1066, 1068, 1074, 1077, 1079, 1081, 59, 1085, 62, 63, 65, 1089, 1092, 1093, 1096, 1097, 81, 91, 109, 121, 634, 123, 141, 142, 170, 172, 684, 185, 186, 199, 210, 725, 217, 737, 229, 232, 238, 247, 254, 266, 269, 276, 281, 803, 807, 808, 297, 811, 814, 816, 819, 313, 827, 830, 831, 320, 321, 838, 841, 843, 846, 847, 848, 337, 851, 853, 854, 345, 346, 861, 862, 863, 349, 351, 866, 865, 356, 871, 872, 873, 874, 363, 875, 365, 878, 877, 880, 879, 371, 885, 374, 891, 896, 386, 901, 905, 910, 912, 915, 916, 918, 920, 923, 413, 926, 928, 417, 932, 933, 421, 423, 936, 424, 428, 941, 429, 943, 946, 947, 948, 438, 953, 444, 957, 452, 453, 454, 967, 966, 457, 974, 975, 976, 979, 983, 984, 985, 988, 477, 990, 479, 994, 998, 999, 1000, 1001, 492, 1004, 1006, 1008, 1013, 1016, 1023], 9: [1025, 1026, 1028, 265, 1035, 1036, 1038, 1041, 1042, 1050, 1054, 1055, 1069, 813, 1071, 1072, 1073, 818, 1075, 820, 821, 824, 825, 1082, 1087, 834, 839, 840, 1098, 856, 860, 864, 870, 103, 887, 892, 893, 898, 902, 904, 907, 908, 911, 913, 921, 931, 934, 937, 940, 950, 958, 960, 965, 455, 971, 978, 986, 991, 992, 995, 996, 1003, 1005, 1007, 1010, 1011, 1017, 1018], 10: [1029, 1032, 1033, 10, 1034, 1037, 1039, 1043, 1044, 1045, 1047, 23, 1049, 27, 1052, 1053, 1059, 1060, 1062, 1067, 45, 1070, 1076, 1078, 1080, 1083, 60, 61, 1084, 1086, 1088, 1090, 1094, 1099, 87, 90, 93, 102, 153, 202, 220, 236, 241, 242, 248, 251, 256, 257, 261, 268, 800, 801, 802, 291, 804, 805, 806, 809, 810, 812, 815, 817, 822, 823, 314, 826, 828, 829, 318, 832, 833, 836, 837, 842, 844, 845, 850, 852, 855, 857, 858, 859, 348, 867, 868, 869, 876, 881, 882, 883, 884, 886, 888, 889, 890, 894, 897, 899, 900, 903, 906, 914, 917, 919, 922, 924, 925, 929, 930, 935, 939, 942, 944, 945, 949, 951, 952, 954, 955, 959, 961, 962, 964, 968, 969, 458, 970, 972, 460, 973, 977, 466, 980, 981, 982, 987, 989, 993, 997, 485, 1002, 490, 1009, 498, 1012, 1014, 1015, 1019, 1020, 1021, 1022], 11: [36, 70, 1100, 77, 1101, 1103, 1106, 1107, 1112, 1115, 1116, 1117, 1119, 1121, 1122, 1123, 1124, 1125, 1126, 1127, 1128, 1129, 106, 1130, 1131, 1133, 1137, 1138, 117, 1142, 1143, 120, 1144, 1146, 1147, 1150, 1152, 1153, 1154, 1156, 1157, 1161, 1162, 1163, 1164, 1167, 1168, 1169, 1171, 1172, 1173, 1176, 1179, 1180, 1181, 158, 1182, 1184, 1186, 1192, 1193, 1194, 1195, 1197, 1198, 1200, 1201, 1205, 1207, 184, 1208, 1209, 1210, 1212, 1214, 1216, 1219, 1224, 1225, 1227, 1228, 1229, 206, 1230, 1232, 1233, 1236, 216, 1243, 1246, 1247, 1248, 224, 227, 1252, 1253, 1254, 1257, 1258, 1263, 1265, 1270, 1271, 1274, 1275, 1279, 258, 1283, 1288, 1291, 1292, 1299, 1301, 1302, 1305, 1308, 1310, 1317, 1321, 298, 1323, 1324, 1329, 1330, 1331, 1332, 309, 1333, 1335, 1334, 1337, 1338, 1340, 1341, 1346, 1350, 1352, 1356, 1357, 1358, 1360, 1362, 1364, 1367, 344, 1370, 1371, 1376, 1378, 1380, 1381, 1382, 1385, 362, 1387, 1388, 1389, 1390, 1394, 1395, 1396, 1397, 1399, 378, 384, 415, 432, 462, 472], 12: [7, 40, 75, 1102, 79, 1104, 1105, 1108, 1110, 1111, 1113, 1114, 92, 94, 95, 1120, 97, 1118, 1132, 1135, 1139, 1140, 119, 1145, 1148, 1149, 1151, 1158, 1159, 1160, 136, 1166, 145, 147, 1174, 150, 1177, 1178, 154, 1183, 159, 1188, 1189, 1190, 1191, 169, 1199, 1202, 1203, 179, 180, 1206, 1213, 1215, 1218, 1220, 1221, 1222, 1223, 198, 1231, 1237, 1238, 1239, 215, 1241, 1242, 1244, 221, 1245, 1249, 1250, 228, 1255, 1256, 1260, 1261, 1267, 243, 1269, 1276, 1280, 1281, 1282, 1284, 1285, 1289, 1290, 1293, 1295, 1297, 1300, 1304, 1306, 1307, 282, 1309, 1313, 1314, 1315, 1316, 292, 1319, 1320, 1325, 1326, 1327, 308, 1336, 315, 316, 1339, 1343, 1345, 1348, 1349, 328, 1353, 1354, 1355, 334, 1361, 1363, 1365, 1366, 343, 1368, 1369, 1372, 1377, 1379, 1386, 366, 1391, 1393, 1398, 381, 394, 399, 400, 405, 410, 425, 437, 459, 491], 13: [1539, 1541, 1542, 1549, 1550, 1552, 1557, 1559, 24, 1561, 1563, 1564, 1566, 1567, 1568, 1574, 1575, 1579, 46, 1587, 1590, 1592, 1596, 317, 1598, 1600, 1601, 1603, 1606, 1608, 1609, 1610, 1612, 1616, 1618, 340, 1621, 1627, 1628, 1632, 1635, 1637, 1639, 359, 1640, 1646, 1650, 1651, 1655, 1400, 1657, 1658, 379, 1404, 1661, 1662, 1660, 1408, 1665, 1410, 1411, 1409, 1669, 1670, 1664, 1667, 1671, 1419, 1675, 1678, 1679, 1680, 401, 1684, 1687, 1431, 1433, 1434, 1690, 420, 1445, 1444, 1448, 1450, 1452, 1453, 1456, 1457, 178, 1460, 1461, 440, 187, 1470, 1471, 193, 1474, 1476, 1480, 1482, 1483, 209, 1489, 1490, 1493, 1496, 1497, 1503, 1509, 1510, 1513, 1517, 1522, 1526, 1527, 1530], 14: [1536, 1537, 2, 1543, 1544, 1545, 1547, 1548, 14, 1551, 16, 1553, 1554, 1555, 1556, 1558, 1565, 1569, 1572, 1576, 1578, 43, 1580, 1581, 1582, 1583, 1584, 48, 1585, 1588, 1591, 1593, 1597, 1599, 1604, 1605, 73, 1611, 1613, 1614, 1615, 1617, 1619, 1620, 1623, 1626, 1629, 1630, 1631, 1633, 1634, 1636, 1641, 1642, 1643, 1644, 1645, 1647, 1648, 1649, 1652, 1653, 1654, 1656, 1663, 130, 1668, 132, 1672, 1673, 1676, 1677, 1681, 1682, 1683, 1685, 1686, 151, 1688, 155, 1692, 1693, 1694, 1695, 1691, 1697, 1698, 235, 237, 244, 252, 280, 287, 1401, 1402, 1403, 1406, 1407, 1412, 1413, 1414, 1415, 1416, 392, 1417, 1420, 1421, 1422, 1423, 1424, 1426, 402, 1427, 1429, 1430, 1437, 1439, 1441, 1443, 1446, 1449, 426, 1454, 1455, 1458, 1459, 1462, 1463, 1464, 441, 1465, 1467, 1468, 1469, 1466, 445, 449, 1473, 1477, 1478, 1479, 1484, 1485, 1487, 467, 1491, 1492, 1494, 1495, 1498, 1499, 1500, 1501, 1504, 480, 1506, 1507, 1505, 1508, 1514, 1515, 1516, 495, 1519, 499, 1524, 1525, 1528, 1529, 1532, 1533], 15: [1538, 1540, 1546, 12, 271, 17, 1560, 1562, 30, 288, 1570, 1571, 1573, 294, 1577, 1586, 307, 1589, 1594, 1595, 322, 1602, 67, 1607, 72, 84, 1622, 86, 1624, 1625, 89, 99, 1638, 361, 115, 373, 1659, 1405, 128, 1666, 131, 1674, 1418, 139, 397, 395, 1425, 1428, 1432, 1689, 1435, 156, 1436, 1438, 1440, 1696, 1442, 1699, 416, 165, 422, 1447, 1451, 173, 183, 1472, 1475, 195, 1481, 1486, 1488, 465, 211, 1502, 481, 486, 1511, 487, 1512, 1518, 1520, 1521, 497, 1523, 250, 1531, 1534, 1535], 16: [34, 44, 68, 122, 140, 157, 1701, 1702, 1704, 168, 1705, 1707, 1708, 1709, 1710, 1712, 1713, 1714, 1716, 1717, 1720, 1721, 1722, 1727, 1728, 1729, 1731, 1734, 1735, 1737, 1738, 1739, 1742, 1743, 1745, 1751, 1756, 1758, 1766, 1769, 1770, 1771, 1772, 1774, 1777, 1778, 1779, 1780, 1782, 1785, 1788, 1791, 1793, 1795, 1796, 1797, 1799, 1801, 1802, 1804, 1805, 1807, 1808, 274, 1813, 1814, 1815, 1816, 1818, 1819, 1820, 1823, 1824, 1826, 1829, 1832, 1833, 1835, 1836, 301, 1837, 1841, 306, 1843, 1848, 312, 1854, 1857, 1858, 1862, 1863, 1864, 1866, 1867, 1868, 331, 1874, 1876, 1879, 1880, 1882, 1885, 1886, 350, 1887, 1890, 1891, 1893, 358, 1896, 1900, 1901, 1903, 1906, 1908, 1910, 1912, 1913, 382, 1919, 1920, 1921, 1923, 1924, 1929, 1930, 1932, 1933, 1934, 1935, 1936, 1937, 1940, 1943, 1945, 1946, 1949, 1958, 1959, 1961, 1963, 1965, 1966, 1967, 430, 1969, 1970, 1973, 1974, 1976, 1978, 1980, 1981, 1982, 1983, 1984, 1986, 1987, 1990, 1994, 483], 17: [1, 5, 8, 32, 33, 35, 39, 69, 76, 107, 110, 112, 113, 127, 146, 160, 162, 1700, 1703, 1706, 1711, 1718, 1719, 1723, 1724, 1725, 1726, 188, 1730, 1732, 1733, 197, 200, 1736, 1740, 1744, 1746, 1748, 1749, 1750, 214, 1753, 1755, 1759, 1760, 1763, 1764, 1765, 1767, 1768, 234, 1773, 239, 1776, 1781, 1784, 1786, 1789, 1792, 1798, 1800, 1803, 1806, 1810, 1811, 1812, 278, 1817, 283, 1822, 1827, 1828, 1830, 1831, 1834, 1838, 1840, 1845, 1846, 1847, 1849, 1852, 1853, 1855, 1859, 1860, 1861, 1865, 1869, 1870, 1871, 1873, 1878, 1884, 1892, 357, 1895, 1898, 1904, 1905, 1911, 375, 1915, 1916, 1918, 383, 1925, 1926, 390, 1931, 396, 1938, 1939, 1941, 406, 1942, 1948, 1951, 1954, 1955, 1957, 1960, 1962, 1964, 1971, 1972, 1975, 1977, 1991, 1993, 1995, 1996, 1997, 488], 18: [1794, 9, 1809, 275, 28, 1821, 1825, 1839, 1842, 1844, 53, 311, 1850, 1851, 1856, 78, 336, 1872, 1875, 1877, 1881, 1883, 1888, 1889, 1894, 1897, 1899, 1902, 1907, 1909, 1914, 125, 1917, 1922, 387, 1927, 1928, 1944, 1947, 1950, 1952, 1953, 1956, 1968, 1715, 181, 1979, 1985, 450, 1988, 1989, 1992, 203, 1741, 1998, 1999, 1747, 212, 1752, 1754, 1757, 1761, 1762, 494, 1775, 246, 1783, 1787, 1790]}

As the community_detection function automatically adds these communtites as labels ot our objects, we can visualise this communities with our standard visualise functionality.

# Visualise the network with communities detected at resolution 1
ms.visualise.visualise_network(
    example_domain,
    network_name='Centroid Delaunay',
    edge_weight_name='Distance',
    visualise_kwargs=dict(
        color_by='Communities : Res = 1',
        marker_size=15,
        scatter_kwargs=dict(linewidth=0.1, edgecolor='black')
    ),
    figure_kwargs=dict(figsize=(10, 7))
)

(<Figure size 1000x700 with 3 Axes>, <Axes: >)

We can see that we have generate communities, which are shown by our labels ‘Communities : Res = 1’ as we defined by the community_label_name parameter. However, we might expect these communities to be the aggregated regions on in the domain. Let’s lower our resolution value to see if can gain more global clusters.

# Perform community detection using the Louvain method with a resolution of 0.3
communities_res_03=ms.networks.community_detection(
    example_domain,
    network_name='Centroid Delaunay',
    edge_weight_name=None,
    community_method='louvain',
    community_method_parameters=dict(resolution=0.3),
    community_label_name='Communities : Res = 0.3'
)

As before, we have added new labels to our domain objects now with the name ‘Communities : Res = 0.3’. We can see what has been added to our domain by printing it out.

print(example_domain)

Domain name: Aggregation
Number of objects: 2001
Collections: ['Cell centres']
Labels: ['Celltype', 'Communities : Res = 1', 'Communities : Res = 0.3']
Networks: ['Centroid Delaunay']
Distance matrices: []

Both labels are there! It’s important we rename our community labels as MuSpAn will overwrite existing labels if we did not. Let’s see if lower the resolution parameter helped.

# Visualise the network with communities detected at resolution 0.3
ms.visualise.visualise_network(
    example_domain,
    network_name='Centroid Delaunay',
    edge_weight_name='Distance',
    visualise_kwargs=dict(
        color_by='Communities : Res = 0.3',
        marker_size=15,
        scatter_kwargs=dict(linewidth=0.1, edgecolor='black')
    ),
    figure_kwargs=dict(figsize=(10, 7))
)

(<Figure size 1000x700 with 3 Axes>, <Axes: >)

By lowering our resolution paramter, we have clustered our nodes into the expected five communities of this aggregated synthetic dataset.

In summary, this highlights just some of the potential of community detection for exploring spatial relationships in networks. This tutorial focused on the basics of community detection, but there are many ways to adapt and extend these methods. For example, you can modify the network type to represent different spatial relationships or enhance the detection process by incorporating edge weights to reflect varying connection strengths. To explore the full range of possibilities, refer to the comprehensive documentation on community detection.