Our code produces an output file with the following sections: The Header, Intermediate Results, and Best Community Structure sections of the produced for the data file FlorentineFamilies.txt, and the WHATEVER section of the output produced for the data file V050-C05-U-D20.txt are shown below.
The header section lists the input data file name and the criterion used to select the next component to partition at each iteration. By default, the sparsest component is selected. The largest component can be selected instead by changing the selection_criterion parameter in MCFCutAlgorithm.txt from 1 to 0. The header for the data file FlorentineFamilies.txt, is shown below.=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= MCF Cut Community Structure Algorithm Data file: FlorentineFamilies.txt Selection Criterion: sparsest component =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=Note that were will be some additional text in the output preceding the header described above if you use the NEOS server to run the code.
The intermediate results for the first two cuts the algorithm makes for the network described by the data file FlorentineFamilies.txt, are shown below. As described in the paper, the algorithm starts by treating the entire network as a single component (community) and then solves the maximum concurrent flow problem (MCFP) to determine a sparse cut. In this case the MCF value is 0.038462 and the cut consists of the single edge (9, 13) as indicated by the lines, "MCF in Component 1 = 0.038462" and "set Cut_Edges := (9,13)", respectively. The density of this cut is 1/26 = 0.038462 as shown on the last line of the output for iteration 1. In this case the cut is indeed a sparsest cut since the cut density is equal to the value of the MCF.=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= Community Structure at Iteration 1 Nodes in Component 1: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 density = 0.190476 Q = 0.000000 Selecting Component 1. MCF in Component 1 = 0.038462 set Saturated_Edges := (2,7) (2,9) (3,5) (3,9) (4,7) (9,13); set Cut_Edges := (9,13); Edges Removed From Component 1: set Cut_Edges := (9,13); Node Pairs Separated by Cut: set Separated_Demands := (1,10) (3,10) (5,10) (7,10) (9,10) (10,14) (13,14) (1,13) (3,13) (5,13) (7,13) (9,13) (10,15) (13,15) (2,10) (4,10) (6,10) (8,10) (10,11) (11,13) (2,13) (4,13) (6,13) (8,13) (10,12) (12,13); Cut Density = 1/26 = 0.038462 =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=Removing the the edge (9, 13) creates two components (subcommunities): one with nodes 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 14, and 15, and the other with nodes 10 and 13. The Q modularity score for this partitioning of the nodes into two components is approximately 0.088750 as shown below.=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= Community Structure at Iteration 2 Nodes in Component 1: 1 2 3 4 5 6 7 8 9 11 12 14 15 density = 0.230769 Nodes in Component 2: 10 13 density = 1.000000 Q = 0.088750As shown above, Components 1 and 2 have densities 0.23 and 1.0, respectively. Thus, the algorithm selects Component 1 as the next component to partition.After solving the MCFP in Component 1, the algorithm determines that the next cut is the set of edges {(3, 9), (4, 7), (12, 14)} as shown below.
Selecting Component 1. MCF in Component 1 = 0.075000 set Saturated_Edges := (2,7) (3,5) (4,7) (7,15) (12,14) (2,9) (3,9) (5,11) (9,12); set Cut_Edges := (3,9) (4,7) (12,14); Edges Removed From Component 1: set Cut_Edges := (3,9) (4,7) (12,14); Node Pairs Separated by Cut: set Separated_Demands := (1,3) (2,3) (3,6) (3,15) (4,12) (5,9) (7,11) (9,14) (1,4) (2,4) (3,7) (4,6) (4,15) (5,12) (7,14) (11,12) (1,5) (2,5) (3,8) (4,7) (5,6) (5,15) (8,11) (11,15) (1,11) (2,11) (3,9) (4,8) (5,7) (6,11) (8,14) (12,14) (1,14) (2,14) (3,12) (4,9) (5,8) (6,14) (9,11) (14,15); Cut Density = 3/40 = 0.075000 =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
If the Q value does not increase after 5 consecutive cuts, the procedure will stop. Otherwise, the procedure continues until each node is its own component. In either case, our code reprints the details of the partition that had the highest Q modularity score. As shown below, this best partition for the Florentine families network consists of 4 components.Stopping criteria reached. =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= Best community structure found has 4 components with Q = 0.397500: Nodes in Component 1: 1 9 12 15 Nodes in Component 2: 2 6 7 8 Nodes in Component 3: 3 4 5 11 14 Nodes in Component 4: 10 13
If the data file has an Intra-Community Edges section indicating an known community structure, then the M score is printed for the best community structure found by the algorithm.The M Score section for V050-C05-U-D20.txt is shown below.
There are 113 inter-community edges between nodes in different communities: set E diff INTRACOM_EDGES := (1,13) (3,47) (6,26) (8,48) (15,35) (19,34) (26,45) (34,49) (1,16) (4,11) (6,46) (9,16) (15,47) (19,43) (27,31) (35,41) (1,19) (4,22) (7,38) (9,32) (15,50) (20,26) (27,40) (35,47) (1,21) (4,25) (7,41) (9,34) (16,26) (20,30) (27,43) (35,49) (1,29) (4,28) (7,43) (9,43) (16,35) (20,31) (28,46) (37,44) (1,36) (4,43) (8,11) (9,50) (16,43) (20,40) (28,48) (38,43) (1,38) (4,44) (8,13) (10,13) (16,48) (21,37) (28,50) (39,44) (2,17) (5,13) (8,14) (10,37) (16,50) (22,41) (30,32) (40,45) (2,18) (5,28) (8,17) (10,39) (17,46) (22,45) (30,35) (2,42) (5,32) (8,27) (11,25) (18,28) (23,46) (30,42) (2,43) (5,40) (8,29) (11,44) (18,30) (23,48) (30,44) (2,44) (5,47) (8,32) (12,28) (18,38) (23,50) (31,46) (3,29) (6,11) (8,35) (12,39) (18,45) (24,37) (32,43) (3,31) (6,22) (8,37) (13,30) (19,25) (24,41) (32,48) (3,34) (6,23) (8,41) (15,21) (19,29) (25,44) (33,41); There are 112 intra-community edges between nodes in the same community: set INTRACOM_EDGES := (1,2) (38,39) (25,26) (12,18) (2,6) (41,49) (31,35) (15,18) (3,10) (43,46) (32,39) (21,22) (8,9) (45,47) (34,37) (23,26) (11,17) (1,6) (39,40) (26,30) (13,15) (2,8) (42,44) (31,39) (16,17) (4,7) (43,48) (33,36) (21,27) (11,12) (46,47) (34,40) (23,30) (12,14) (1,8) (41,43) (29,30) (13,20) (3,5) (42,46) (32,35) (16,20) (5,6) (44,46) (33,38) (22,30) (11,14) (47,48) (37,38) (24,30) (12,17) (2,4) (41,47) (31,34) (15,16) (3,9) (43,45) (32,37) (17,20) (7,10) (45,46) (34,35) (23,25) (11,16) (1,4) (38,40) (25,28) (12,19) (2,7) (41,50) (31,36) (15,19) (4,6) (43,47) (33,35) (21,24) (8,10) (45,50) (34,39) (23,29) (12,13) (1,7) (41,42) (27,29) (13,16) (3,4) (42,45) (31,40) (16,19) (4,9) (44,45) (33,37) (22,26) (11,13) (46,50) (36,39) (24,25) (12,16) (2,3) (41,46) (31,32) (14,15) (3,8) (42,49) (32,36) (17,18) (6,8) (44,48) (33,39) (23,24) (11,15) (49,50); There are 111 algorithm-labeled inter-community edges: set INTER := (1,13) (3,34) (6,22) (8,35) (12,28) (18,30) (22,45) (30,44) (1,16) (3,47) (6,23) (8,37) (12,39) (18,38) (23,46) (31,46) (1,19) (4,11) (6,26) (8,41) (13,30) (18,45) (23,48) (32,43) (1,21) (4,22) (6,46) (8,48) (15,21) (19,25) (23,50) (32,48) (1,29) (4,25) (7,38) (9,16) (15,35) (19,29) (24,37) (33,41) (1,36) (4,28) (7,41) (9,32) (15,47) (19,34) (24,41) (34,49) (1,38) (4,43) (7,43) (9,34) (15,50) (19,43) (25,28) (35,41) (2,17) (4,44) (8,11) (9,43) (16,26) (20,26) (25,44) (35,47) (2,18) (5,13) (8,13) (9,50) (16,35) (20,30) (26,45) (35,49) (2,42) (5,28) (8,14) (10,13) (16,43) (20,31) (27,29) (37,44) (2,43) (5,32) (8,17) (10,37) (16,48) (20,40) (27,43) (38,43) (2,44) (5,40) (8,27) (10,39) (16,50) (21,27) (30,32) (39,44) (3,29) (5,47) (8,29) (11,25) (17,46) (21,37) (30,35) (40,45) (3,31) (6,11) (8,32) (11,44) (18,28) (22,41) (30,42); There are 114 algorithm-labeled intra-community edges: set INTRA := (1,2) (4,6) (12,14) (17,18) (27,31) (32,39) (41,42) (44,46) (1,4) (4,7) (12,16) (17,20) (27,40) (33,35) (41,43) (44,48) (1,6) (4,9) (12,17) (21,22) (28,46) (33,36) (41,46) (45,46) (1,7) (5,6) (12,18) (21,24) (28,48) (33,37) (41,47) (45,47) (1,8) (6,8) (12,19) (22,26) (28,50) (33,38) (41,49) (45,50) (2,3) (7,10) (13,15) (22,30) (29,30) (33,39) (41,50) (46,47) (2,4) (8,9) (13,16) (23,24) (31,32) (34,35) (42,44) (46,50) (2,6) (8,10) (13,20) (23,25) (31,34) (34,37) (42,45) (47,48) (2,7) (11,12) (14,15) (23,26) (31,35) (34,39) (42,46) (49,50) (2,8) (11,13) (15,16) (23,29) (31,36) (34,40) (42,49) (3,4) (11,14) (15,18) (23,30) (31,39) (36,39) (43,45) (3,5) (11,15) (15,19) (24,25) (31,40) (37,38) (43,46) (3,8) (11,16) (16,17) (24,30) (32,35) (38,39) (43,47) (3,9) (11,17) (16,19) (25,26) (32,36) (38,40) (43,48) (3,10) (12,13) (16,20) (26,30) (32,37) (39,40) (44,45); The algorithm correctly labeled 108 out of 113 intra-community edges: set CORRECT_INTERCOM_EDGES := (1,13) (3,34) (6,22) (8,35) (12,28) (18,30) (23,46) (32,48) (1,16) (3,47) (6,23) (8,37) (12,39) (18,38) (23,48) (33,41) (1,19) (4,11) (6,26) (8,41) (13,30) (18,45) (23,50) (34,49) (1,21) (4,22) (6,46) (8,48) (15,21) (19,25) (24,37) (35,41) (1,29) (4,25) (7,38) (9,16) (15,35) (19,29) (24,41) (35,47) (1,36) (4,28) (7,41) (9,32) (15,47) (19,34) (25,44) (35,49) (1,38) (4,43) (7,43) (9,34) (15,50) (19,43) (26,45) (37,44) (2,17) (4,44) (8,11) (9,43) (16,26) (20,26) (27,43) (38,43) (2,18) (5,13) (8,13) (9,50) (16,35) (20,30) (30,32) (39,44) (2,42) (5,28) (8,14) (10,13) (16,43) (20,31) (30,35) (40,45) (2,43) (5,32) (8,17) (10,37) (16,48) (20,40) (30,42) (2,44) (5,40) (8,27) (10,39) (16,50) (21,37) (30,44) (3,29) (5,47) (8,29) (11,25) (17,46) (22,41) (31,46) (3,31) (6,11) (8,32) (11,44) (18,28) (22,45) (32,43); The algorithm correctly labeled 109 out of 112 intra-community edges: set CORRECT_INTRACOM_EDGES := (1,2) (38,39) (25,26) (21,22) (13,15) (11,12) (46,47) (34,40) (3,10) (43,46) (32,39) (26,30) (29,30) (13,20) (3,5) (42,46) (11,17) (1,6) (39,40) (33,36) (33,38) (22,30) (11,14) (47,48) (16,17) (4,7) (43,48) (41,43) (41,47) (31,34) (15,16) (3,9) (23,30) (12,14) (1,8) (44,46) (45,46) (34,35) (23,25) (11,16) (32,35) (16,20) (5,6) (2,4) (2,7) (41,50) (31,36) (15,19) (37,38) (24,30) (12,17) (7,10) (8,10) (45,50) (34,39) (23,29) (43,45) (32,37) (17,20) (12,19) (13,16) (3,4) (42,45) (31,40) (1,4) (38,40) (33,35) (21,24) (22,26) (11,13) (46,50) (36,39) (4,6) (43,47) (41,42) (33,37) (31,32) (14,15) (3,8) (42,49) (12,13) (1,7) (44,45) (41,46) (33,39) (23,24) (11,15) (49,50) (16,19) (4,9) (2,3) (44,48) (41,49) (31,35) (15,18) (24,25) (12,16) (6,8) (2,6) (45,47) (34,37) (23,26) (32,36) (17,18) (12,18) (8,9) (2,8) (42,44) (31,39); m = 225 M = 0.964444Since the algorithm correctly labeled 217 out of the 225 edges in the network, it gets an M score of 217/225 = 0.96 for the network described by V050-C05-U-D20.txt.