Our code was written assuming that the input data file contains the following sections: The format for each of these sections is described below using the data file V050-C05-U-D20.txt as an example.
This is an optional section that allows the user to write a description of the social network represented by the data file. In AMPL a # character at the beginning of a line means that the entire line is a comment. So, the lines shown below are comments for the reader that are ignored by AMPL.# This is a randomly generated 50-node graph with 5 subcommunities similar # the graphs described in "The Use of Sparsest Cuts to Reveal the Hierarchical Community Structure # of Social Networks" by Mann, Matula, and Olinick. # The subcommunities are nodes 1 through 10, nodes 11 through 20, nodes 21 through 30, etc.
This optional section of the datafile passes the file name to AMPL so that our code can print it at the beginning of its output. This is done with a single line that starts with "param filename :=" followed by the name of the data file and ending with a semicolon (;). For example, the line below from V050-C05-U-D20.txt passes the name of the file to AMPL.param filname := V050-C05-U-D20.txt;
As stated in the paper, we assume that the nodes of the graph G = (V, E) are numbered 1, 2, 3, ..., n where n = |V|. Thus, this section specifies the number of nodes in the network, n. This is done with a single line that starts with "param n :=" followed by the value of n and ending with a semicolon (;). For example, the line below from V050-C05-U-D20.txt indicates that there are fifty (50) nodes in the network.param n := 50;
This section lists the edges of the social network. The syntax for list the edges is the line "set E :=", followed by a listing of ordered pairs representing the edges which is then followed by a semicolon (;) as shown below. Note that the edge between nodes i and j, where i < j, is listed as (i, j).set E := (1, 2) (1, 4) (1, 6) (1, 7) (1, 8) (1, 13) (1, 16) (1, 19) (1, 21) (1, 29) (1, 36) (1, 38) (2, 3) (2, 4) (2, 6) (2, 7) (2, 8) (2, 17) (2, 18) (2, 42) (2, 43) (2, 44) (3, 4) (3, 5) (3, 8) (3, 9) (3, 10) (3, 29) (3, 31) (3, 34) (3, 47) (4, 6) (4, 7) (4, 9) (4, 11) (4, 22) (4, 25) (4, 28) (4, 43) (4, 44) (5, 6) (5, 13) (5, 28) (5, 32) (5, 40) (5, 47) (6, 8) (6, 11) (6, 22) (6, 23) (6, 26) (6, 46) (7, 10) (7, 38) (7, 41) (7, 43) (8, 9) (8, 10) (8, 11) (8, 13) (8, 14) (8, 17) (8, 27) (8, 29) (8, 32) (8, 35) (8, 37) (8, 41) (8, 48) (9, 16) (9, 32) (9, 34) (9, 43) (9, 50) (10, 13) (10, 37) (10, 39) (11, 12) (11, 13) (11, 14) (11, 15) (11, 16) (11, 17) (11, 25) (11, 44) (12, 13) (12, 14) (12, 16) (12, 17) (12, 18) (12, 19) (12, 28) (12, 39) (13, 15) (13, 16) (13, 20) (13, 30) (14, 15) (15, 16) (15, 18) (15, 19) (15, 21) (15, 35) (15, 47) (15, 50) (16, 17) (16, 19) (16, 20) (16, 26) (16, 35) (16, 43) (16, 48) (16, 50) (17, 18) (17, 20) (17, 46) (18, 28) (18, 30) (18, 38) (18, 45) (19, 25) (19, 29) (19, 34) (19, 43) (20, 26) (20, 30) (20, 31) (20, 40) (21, 22) (21, 24) (21, 27) (21, 37) (22, 26) (22, 30) (22, 41) (22, 45) (23, 24) (23, 25) (23, 26) (23, 29) (23, 30) (23, 46) (23, 48) (23, 50) (24, 25) (24, 30) (24, 37) (24, 41) (25, 26) (25, 28) (25, 44) (26, 30) (26, 45) (27, 29) (27, 31) (27, 40) (27, 43) (28, 46) (28, 48) (28, 50) (29, 30) (30, 32) (30, 35) (30, 42) (30, 44) (31, 32) (31, 34) (31, 35) (31, 36) (31, 39) (31, 40) (31, 46) (32, 35) (32, 36) (32, 37) (32, 39) (32, 43) (32, 48) (33, 35) (33, 36) (33, 37) (33, 38) (33, 39) (33, 41) (34, 35) (34, 37) (34, 39) (34, 40) (34, 49) (35, 41) (35, 47) (35, 49) (36, 39) (37, 38) (37, 44) (38, 39) (38, 40) (38, 43) (39, 40) (39, 44) (40, 45) (41, 42) (41, 43) (41, 46) (41, 47) (41, 49) (41, 50) (42, 44) (42, 45) (42, 46) (42, 49) (43, 45) (43, 46) (43, 47) (43, 48) (44, 45) (44, 46) (44, 48) (45, 46) (45, 47) (45, 50) (46, 47) (46, 50) (47, 48) (49, 50) ;
This section specifies the edge weights. There is a line specifying The section begins with the line "param C :=", then has a line for each edge, and ends with a semicolon (;). The the syntax for the line for edge (i, j) with weight Cij is shown below.i j CijFor example, in V050-C05-U-D20.txt edge (1, 2) has weight C12 = 2.166, and so the corresponding line is shown below.1 2 2.166Note that by default the code assumes that an edge's weight is 1, and so this section can be omitted in the data file for an unweighted graph. For example, this data file for the Florentine families network does not have this section. The complete edge weight section for V050-C05-U-D20.txt is shown below.param C := 1 2 2.166 1 4 2.654 1 6 1.342 1 7 2.062 1 8 1.676 1 13 1.481 1 16 0.455 1 19 1.103 1 21 0.742 1 29 1.002 1 36 0.723 1 38 0.519 2 3 2.636 2 4 2.144 2 6 2.766 2 7 1.998 2 8 1.84 2 17 0.694 2 18 0.992 2 42 1.18 2 43 0.468 2 44 1.352 3 4 1.234 3 5 2.88 3 8 0.714 3 9 1.078 3 10 2.836 3 29 0.725 3 31 1.587 3 34 0.927 3 47 1.185 4 6 2.104 4 7 1.268 4 9 2.19 4 11 0.793 4 22 0.875 4 25 1.205 4 28 0.639 4 43 1.473 4 44 0.976 5 6 3.108 5 13 1.124 5 28 1.006 5 32 0.532 5 40 1.146 5 47 0.105 6 8 2.122 6 11 0.567 6 22 1.872 6 23 1.438 6 26 0.517 6 46 1.345 7 10 2.176 7 38 1.564 7 41 1.072 7 43 0.853 8 9 2.828 8 10 2.196 8 11 0.761 8 13 0.062 8 14 1.602 8 17 1.052 8 27 0.697 8 29 0.605 8 32 0.655 8 35 1.506 8 37 1.543 8 41 1.444 8 48 1.046 9 16 0.977 9 32 1.467 9 34 0.803 9 43 1.225 9 50 1.455 10 13 1.304 10 37 1.46 10 39 1.238 11 12 2.506 11 13 3.346 11 14 3.186 11 15 3.326 11 16 2.546 11 17 0.988 11 25 1.212 11 44 1.624 12 13 2.404 12 14 2.762 12 16 2.874 12 17 2.414 12 18 2.286 12 19 3.596 12 28 0.421 12 39 0.613 13 15 2.088 13 16 1.766 13 20 2.872 13 30 1.63 14 15 2.486 15 16 1.278 15 18 2.672 15 19 1.07 15 21 0.967 15 35 0.669 15 47 1.062 15 50 1.306 16 17 2.128 16 19 1.72 16 20 0.636 16 26 1.603 16 35 0.496 16 43 0.728 16 48 0.622 16 50 0.29 17 18 2.844 17 20 2.92 17 46 0.831 18 28 0.847 18 30 0.574 18 38 0.826 18 45 1.57 19 25 1.291 19 29 0.376 19 34 1.61 19 43 1.092 20 26 1.22 20 30 1.344 20 31 0.563 20 40 0.91 21 22 1.444 21 24 3 21 27 0.98 21 37 0.848 22 26 2.73 22 30 1.374 22 41 1.507 22 45 0.948 23 24 2.936 23 25 2.144 23 26 3.722 23 29 2.672 23 30 2.022 23 46 1.586 23 48 0.853 23 50 0.123 24 25 1.976 24 30 2.672 24 37 0.491 24 41 0.659 25 26 2.68 25 28 2.044 25 44 1.245 26 30 1.14 26 45 1.022 27 29 1.04 27 31 1.699 27 40 1.567 27 43 1.092 28 46 0.777 28 48 1.115 28 50 0.134 29 30 3.174 30 32 1.684 30 35 1.565 30 42 0.369 30 44 1.576 31 32 2.376 31 34 3.278 31 35 2.252 31 36 1.766 31 39 2.906 31 40 1.298 31 46 0.771 32 35 2.318 32 36 1.692 32 37 2.154 32 39 1.16 32 43 0.856 32 48 0.55 33 35 0.492 33 36 3.048 33 37 3.488 33 38 3.19 33 39 3.136 33 41 0.993 34 35 1.52 34 37 3.292 34 39 2.138 34 40 3.702 34 49 0.884 35 41 1.216 35 47 0.526 35 49 1.031 36 39 3.432 37 38 1.758 37 44 1.244 38 39 1.316 38 40 2.386 38 43 0.482 39 40 1.916 39 44 0.667 40 45 1.359 41 42 2.85 41 43 2.284 41 46 1.182 41 47 1.36 41 49 2.718 41 50 1.448 42 44 1.874 42 45 1.616 42 46 1.126 42 49 0.862 43 45 1.628 43 46 1.488 43 47 2.258 43 48 3.242 44 45 2.908 44 46 2.87 44 48 2.76 45 46 1.612 45 47 1.832 45 50 0.19 46 47 2.082 46 50 0.81 47 48 0.516 49 50 3.418 ;
This section specifies the subcommunities of the social network by listing the subset of edges that are intra-community edges. This set is denoted by CW in the paper. In the example data file edge (1, 2) is an intra-community edge because nodes 1 and 2 are in the same subcommunity. Likewise edge (36, 39) is an intra-community edge. Nodes 1 and 36 are in different subcommunities, and so edge (1, 36) is an inter-community edge and thus not listed in this section. The syntax for listing the intra-community edges is the line "set INTRACOM_EDGES :=" followed by the list of intra-community edges which is then followed by a semicolon (;) as shown below.set INTRACOM_EDGES := (1,2) (3,10) (11,17) (16,17) (23,30) (32,35) (37,38) (43,45) (1,4) (4,6) (12,13) (16,19) (24,25) (32,36) (38,39) (43,46) (1,6) (4,7) (12,14) (16,20) (24,30) (32,37) (38,40) (43,47) (1,7) (4,9) (12,16) (17,18) (25,26) (32,39) (39,40) (43,48) (1,8) (5,6) (12,17) (17,20) (25,28) (33,35) (41,42) (44,45) (2,3) (6,8) (12,18) (21,22) (26,30) (33,36) (41,43) (44,46) (2,4) (7,10) (12,19) (21,24) (27,29) (33,37) (41,46) (44,48) (2,6) (8,9) (13,15) (21,27) (29,30) (33,38) (41,47) (45,46) (2,7) (8,10) (13,16) (22,26) (31,32) (33,39) (41,49) (45,47) (2,8) (11,12) (13,20) (22,30) (31,34) (34,35) (41,50) (45,50) (3,4) (11,13) (14,15) (23,24) (31,35) (34,37) (42,44) (46,47) (3,5) (11,14) (15,16) (23,25) (31,36) (34,39) (42,45) (46,50) (3,8) (11,15) (15,18) (23,26) (31,39) (34,40) (42,46) (47,48) (3,9) (11,16) (15,19) (23,29) (31,40) (36,39) (42,49) (49,50) ;