复杂网络社团结构识别算法

=================================================================== == Radatools 1.1 == == == == Copyright (c) 2010 by == == == == Sergio Gomez (sergio.gomez@urv.cat) == == Alberto Fernandez (alberto.fernandez@urv.cat) == == Javier Borge-Holthoefer (javier.borge@urv.cat) == == Alex Arenas (alexandre.arenas@urv.cat) == == == == 17/11/2009 == == == == All rights reserved, see LICENSE.txt == =================================================================== ----------- Description ----------- Radatools is a set of freely distributed Windows programs to analyze Complex Networks. In particular, it includes a very useful program for Communities Detection. The program 'Communities_Detection' takes a complex network in Pajek format (*.net) and outputs the best partition found in Lol format (*-lol.txt). Since probably you will not have the network in Pajek format, we have added programs to create Pajek network files from text files with lists of links, 'List_To_Net', and from adjacency (or weights) matrices, 'Matrix_To_Net'. Another useful program is 'Connected_Subgraphs', which checks if a network is connected and, if not, creates separate network files for each connected component. The output of 'Communities_Detection' is a partition in a text format we call 'Lol format' (usually *-lol.txt). It contains information about the number of elements in the partition, the number of communities (or lists of elements), the size of each community, and the indices of the elements which belong to each community. The program 'Convert_Lol_To_Clu' converts a partition in Lol format to Pajek (*.clu) format. And 'Reformat_Partition' replaces the indices of the elements by their respective names in the network Pajek file, allowing also to group elements in a way more appropriate for the analysis of the communities, or in a more readable form. --------------------- Communities detection --------------------- The program 'Communities_Detection' implements several algorithms for the optimization of modularity [1]. It is prepared to work with - unweighted [1] and weighted [2] networks - undirected [1] and directed [3] networks - positive [1] and signed [4] networks The main types of (directed and undirected) modularity definitions optimized are: - UN: unweighted modularity [1,3] - WN: weighted modularity [2,3] - WS: weighted modularity with positive and negative links [4] The optimization algorithms implemented are: - (h): exhaustive search - (t): tabu search [5] - (e): extremal optimization [6] - (s): spectral optimization [7] - (f): fast algorithm [8] - (r): fine-tuning by reposition - (b): fine-tuning by bootstrapping based on tabu search [5] It is possible to combine different optimization algorithms in a single run of the communities detection program. For instance, a possible heuristic is 'trfr', which consists in a tabu search, followed by a reposition fine-tuning, followed by the fast-algorithm, and finally another reposition fine-tuning. Some heuristics have a stochastic behavior, thus several executions could lead to different optimal partitions. In 'Communities_Detection' you can specify the number of repetitions to execute each of the heuristics, before proceeding to the next one. If the partition file exists before the execution, it is taken as the initial partition. Thus, running the program twice with heuristics 'trfr' is equivalent to running it once with heuristics 'trfrtrfr'. There are four levels of verbosity: - (n): none - (s): summary - (p): progress - (v): verbose For long runs, 'p' or 'v' should be preferred since they save in temporary files the best intermediate partitions. ---------- Heuristics ---------- A short description of each heuristic follows: - Exhaustive search (h): only possible for very small networks. - Tabu search (t): usually the most accurate heuristic for medium sized networks, however it cannot deal with large networks. If you use it, please cite [5]. - Extremal optimization (e): good tradeoff between accuracy and execution time, and useful for networks too large for tabu search. If you use it, please cite [6]. - Spectral optimization (s): very fast heuristic and useful for large networks, but with low accuracy. The implementation does not cope with directed networks. If you use it, please cite [7]. - Fast algorithm (f): very fast heuristic and useful for large networks, but with low accuracy. It may be used as a fine-tuning algorithm when combined with others. If you use it, please cite [8]. - Reposition algorithm (r): very fast fine-tuning algorithm. - Bootstrapping algorithm (f): fine-tuning algorithm based on tabu search. If you use it, please cite [5]. The recommended strategy is the following: - For networks with less than 1000 nodes, try "trfr" with 1 repetition - If succeeds in a reasonable time, erase the previous result and increment the number of repetitions to 10, 30 or a larger number - To check if the partition may be improved, try "esrfrtrfr" with some repetitions, and without erasing the previous partition - For larger networks, do the same but starting with "esrfr" or "esbrfbr" -------- Contents -------- The detailed list of programs available in this version of Radatools and its organization in folders is as follows: 01-Prepare_Network: - List_To_Net: Convert a file with the list of links of a graph into a network file in Pajek format (*.net) - Matrix_To_Net: Convert a file with a graph in matrix form into a network file in Pajek format (*.net) - Connected_Subgraphs: Split a network in Pajek format into its connected components 02-Find_Communities: - Communities_Detection: Community detection in complex networks by optimization of modularity 03-Reformat_Partition: - Convert_Lol_To_Clu: Convert a file with a partition in Lol format into a file with a partition in Pajek format (*.clu) - Reformat_Partition: Reformat a partition in Lol format changing nodes' indices by nodes' names ----- Hints ----- - Each folder contains program files (*.exe), sample script files (*.bat or *.sh) for each program, and some test files. - It is highly recommended to have a look at the sample script and test files (e.g. with Notepad, vi or nano) before proceeding with your data. - Each folder has a "results' subfolder with the outputs obtained after running the sample scripts with the given test files. These result files may differ from the ones obtained running the sample scripts, due to the stochastic behavior of some of the implemented algorithms (e.g. 'Communities_Detection'). - The programs may be run directly from command line, but it is more convenient to create script files (*.bat or *.sh) which call the programs with the necessary lists of parameters. Thus, it is recommended that you make a copy of the companion script file (*.bat or *.sh) of the program you want to use, edit it with a text editor (e.g. Notepad, vi or nano), and run it. - When you run a program without parameters, an 'Usage' message shows the list of expected parameters. - Read 'LICENSE.txt' to know the conditions to use Radatools. -------- Progr