edit SideBar

CFinder manual

Top

1.  README

Copyright (c) Department of Biological Physics,
Eötvös University, Budapest. 2005-2010.

For non-profit users the permission to use, copy, and modify
this software and its documentation for any purpose is hereby
granted without fee, provided that the above copyright notice
appears in all copies and that both the copyright notice and
this permission notice appear in supporting documentation.

All other users are kindly requested to contact the holders of
the license (see below for contact information).

The holders of the license make no representations about the
suitability of this software for any purpose. It is provided
"as is" without express or implied warranty.

Top

2.  Quick start

# you can use comments (this line)
# and empty lines

nodeA nodeB 10.3
nodeB nodeC 3.55
nodeA nodeC 4.23

Top

2.1  Command line version (batch, no visualization)

The executable CFinder_commandline is the command line version of CFinder. (Use CFinder_commandline64 on an amd64 Linux) It uses no visualization. All parameters that can be used in the GUI can be set with command-line parameters, see the output of CFinder_commandline –h.

Top

2.2  What are the data in the output files?

Each output file contains a header. If you open one output file with a text editor (we recommend NotePad++ on Windows, emacs on Linux and TextEdit on the Mac), then you will find that the first few lines start with a "#" sign. These are the comment lines of the file and describe the contents of the given file.

Top

2.3  CFinder is very slow for my network, can you help?

Yes. Please, contact us at CFinder@hal.elte.hu .

Note that there can be several reasons for an unusually slow community finding. One of the most frequently occurring reasons is that the "core" (the most densely connected region) of the network contains several strongly overlapping cliques of size 50-100 (or above). You can read further details about the amount of CPU time and memory used by CFinder in the sections on CPU and memory requirements and on how to increase the amount of memory CFinder uses. There are some other hints in the FAQ here and here.

Top

3.  Theoretical background

3.1  The Clique Percolation Method

The original Clique Percolation Method (CPM) used by CFinder is designed to locate the k-clique communities of unweighted, undirected networks. (Extended versions of this algorithm, included in CFinder can handle directed and weighted networks as well, see below.) This community definition is based on the observation that a typical member in a community is linked to many other members, but not necessarily to all other nodes in the community. In other words, a community can be interpreted as a union of smaller complete (fully connected) subgraphs that share nodes. Such complete subgraphs in a network are called k-cliques, where k refers to the number of nodes in the subgraph, and a k-clique-community is defined as the union of all k-cliques that can be reached from each other through a series of adjacent k-cliques. Two k-cliques are said to be adjacent if they share k-1 nodes.

An illustration of these communities can be given by k-clique template rolling. A k-clique template can be thought of as an object that is isomorphic to a complete graph of k nodes. Such a template can be placed onto any k-clique of the network, and rolled to an adjacent k-clique by relocating one of its nodes and keeping its other k-1 nodes fixed. Thus, the k-clique-communities of a graph are all those subgraphs that can be fully explored by rolling a k-clique template in them but cannot be left by this template.

The CPM was inspired by the fact that the k-clique communities also correspond to percolation clusters in the k-clique adjacency graph of the system. The nodes of the k-clique adjacency graph represent the k-cliques of the original network, and there is an edge between two nodes if the corresponding two k-cliques are adjacent.

The advantages of the above community definition are the following:

• it is not too restrictive (unlike cliques that require each node to be connected to all other nodes),
• it is based on the density of links,
• it is local,
• it does not yield cut-nodes or cut-links (whose removal would disjoin the community),
• and it allows overlaps: (i) a node can be a member of several different communities at the same time, and (ii) communities can overlap with each other by sharing nodes. Naturally, the communities also constitute a network with these overlaps as their links. The number of such links of a community can be called its community degree.

Top

3.2  Outline of the community finding algorithm

For details on the algorithm used by CFinder, see supplemental information for the 2005 Nature paper

• The k-clique community finding algorithm implemented in CFinder first extracts all such complete subgraphs of the network that are not included in any larger complete subgraph. These maximal complete subgraphs are simply called cliques (the difference between k-cliques and cliques is that k-cliques can be subsets of larger complete subgraphs).
• Once the cliques are located, the clique-clique overlap matrix is prepared. In this symmetric matrix each row (and column) represents a clique and the matrix elements are equal to the number of common nodes between the corresponding two cliques, while each diagonal entry is equal to the size of that clique.
• The k-clique-communities for a given value of k are equivalent to such connected clique components in which the neighboring cliques are linked to each other by at least k-1 common nodes. These components can be found by erasing every off-diagonal entry smaller than k-1 and every diagonal element smaller than k in the matrix, replacing the remaining elements by one, and then carrying out a component analysis of this matrix. The resulting separate components will be equivalent to the different k-clique-communities.

Top

3.3  Directed and weighted networks

The original CPM method, as described above, can only handle undirected, unweighted networks. CFinder, however, also contains algorithms for handling directed (CPMd) and weighted (CPMw) networks. These are natural extensions of the CPM method. In both case the key idea is that one can add extra criteria for a clique to be used when building the community.

For details on the criteria and the algorithm, see the 2007 papers in New J. Phys

Top

3.4  Implementation details

Note that due to the extra criteria used for deciding which cliques to use, the communities can't be generated from the maximal cliques of the graph, so for CPMw CFinder simply directly creates the communities by growing a single k-clique (the CPMd uses maximal directed cliques).

Top

4.  Download and Installation

4.1  How to download and install CFinder

CFinder can be downloaded from http://CFinder.org. For unpacking the downloaded zip file, we suggest 7zip on Windows, the standard Linux unzip utility, and Aladdin Stuffit Expander on the Mac. (Note: winzip had problems with unpacking some of the earlier releases.)

CFinder uses the Java Runtime Environment version 1.5 or higher by Sun. (CFinder might work with non-Sun java runtimes, but it is not tested.) Type java –version (Windows users: at the DOS prompt, Linux and Mac users: at the command prompt) to see if you have this version installed on your computer. If an error occurs when executing the "java" command, or the version number is below 1.4, or you have a different Java engine, then please, download J2SE JRE from http://www.java.com/en/download/index.jsp and install it (On Linux, using your distribution's package manager is recommended). Having completed the installation of Java, you will need to make sure that your operating system can find it. On Windows systems this is carried out automatically, but when installing by hand on some Linux systems you need to append to your PATH environment variable the following: $JAVA_HOME/bin, where $JAVA_HOME is the name of the directory where you installed Sun’s J2SE JRE.

A note for Solaris users: you will also have to download the -solaris.zip file and replace the libcommfind.so and CFinder_commandline files with the ones in the solaris .zip file.

Top

4.2  How to start CFinder

To launch the GUI version of CFinder, use the start.bat script on Windows and start.sh on Linux, Mac and Solaris.

The executable CFinder_commandline is the command line version of CFinder. (Use CFinder_commandline64 on an amd64 Linux) It uses no visualization. All parameters that can be used in the GUI can be set with command-line parameters, see the output of CFinder_commandline –h.

Top

4.3  Files and directories

These are the directories and files in the downloadable package of CFinder.

Top

4.4  A note for Mac OS X versions below 10.4 (Tiger)

If automatic updates are not enabled on your Mac, please update your system before using CFinder. Click on the Apple icon in the top left corner and select "Software Update". Make sure to update both Java and Mac OS X to their most recent versions.

Top

4.5  A note for Linux users

On several Linux systems the default Java engine is not the Java Runtime Environment by Sun and/or there are various other Java engines available.

Java is meant to be platform independent. Unfortunately, the different Java engines show sometimes unexpected differences in the way they run the same Java program. We suggest that you should use the Java Runtime Environment version 1.5 by Sun or higher to run CFinder.

Top

4.6  How much memory and CPU time does CFinder need for my network?

The amount of memory needed for the community finding in your network will be most strongly influenced by the number and the overlaps of cliques / dense regions. Of course, the number of nodes is also important, but the necessary CPU time and memory grow only slowly with the number of nodes.

A short explanation follows here. (Jump to the next paragraph, if you want to receive practical advice.) A linear chain of nodes with a few loops on it contains only a small number of small cliques, e.g., triangles, and CFinder will need little memory and CPU time for this network. If the input network is a complete graph (each node is connected to all other nodes) is one clique, and resources of your computer needed for this network will be small again. Between these two extremes are those networks that need more memory and CPU time. These contain a high number of large, overlapping cliques: there are large dense regions in the network, but a typical node is not connected to all other nodes. (Remember that a clique is a complete subgraph not contained by any other complete subgraph.)

In practice, the best way to run CFinder on a large network is to use confidence values for the links. The confidence (or “weight”) of each link can be used for filtering the links in the “New Community Finding” dialog. At the first run, set a high value for the lower cutoff in the “New Community Finding” dialog. This will remove many links from the network and the remaining graph that CFinder receives for analysis will be sparse. Later, you can run CFinder again (File > Open new community) and decrease step by step the lower threshold to leave more and more links in the network.

Top

4.7  How do I increase the amount of memory used by CFinder?

If you are using a large network and/or a network with many overlapping dense regions, and CFinder stops with an error message explaining that more memory would be necessary, then in the start batch file increase the memory requested by CFinder from your operating system. In the start batch files (start.bat on Windows and start.sh on Linux and Mac) you will find two switches: "-Xmx224m" and "-Xss32m". Increase both numbers (224 and 32) such that their sum remains smaller than the physical memory of your computer.

Top

5.  The graphical user interface

5.1  The File menu

Open new network

Opens the “New Community Finding” dialog. In this dialog click on browse to open a data file containing the edges of a network. In the program package that you have downloaded and unpacked there are sample network files in the demo/ subdirectory.

The main CFinder window with the “New Community Finding” and the “Open file” dialogs.

Once you have selected the input file, you can set the parameters to use. Most of these parameters are optional, leave the associated checkbox empty to not use the given setting.

Filter edges

This feature can be used to run CFinder on a filtered version of your network. Use the fields to the left and right from the word weight to select a lower and upper cutoff for link weights. For the community finding only those links of the network will be used whose weights (as listed in the third column of the input file) are between the lower and the upper cutoff values. All other links of the network will be discarded before the community finding starts. If the input network file provides no weights for the links, then CFinder will ignore the cutoff values that you enter in the “New Community Finding” dialog.

Select algorithm

For the weighted algorithm (CPMw), also specify an intensity threshold, (see the paper on CPMw for how this is used) and you can also optionally limit the algorithm to a given k value. (only results for this given k will be calculated.)

Run

Click on run to start the community finding. While the communities of the network are computed, you will see progress bars indicating the status of the community search.

Top

Output directory (for the computed cliques, communities, etc.)

To save the results, CFinder creates a new directory. If the directory already exists, CFinder will ask whether to overwrite it, since that could result in loss of data. This directory will be created at the same location as the analyzed input network file, and the name of the output directory will be the name of the input network file plus a “_files” suffix. If you select a lower and upper threshold for the links weights, then these two weights will be appended to the name of the output directory after “_files”, e.g., if the input file myNetwork.txt is analyzed with the lower and upper thresholds 0.2 and 0.5, then the output directory will be called myNetwork.txt_files_0.2_w_0.5. CFinder writes all the computed communities, cliques, and statistics into this directory. Note that CFinder refuse to overwrite an existing directory to avoid loosing data.

Top

Open communities (choose directory with previously computed data)

If you have already run CFinder for a network and created an output directory, you can view the results again by selecting File > Open communities.

The main CFinder window with the dialog for opening already computed communities.

Top

5.2  Approximate (fast) clique finding

Select this option at the bottom of the “New Community Finding” dialog.

• time limit: maximum time per node in seconds (suggested value: 1 - 10)

Approximate (fast) clique finding. Select "Approximation" and select the time limit.

Networks (both small and large) may contain many large overlapping cliques. CFinder allows setting an optional time limit (in seconds) for the time to spend on each node of the network. If exploring the neighborhood of the given node would take longer than this, CFinder will (temporarily) give up and proceed to the next node. Once all nodes have been tried, it will try those where it gave up previously (since processing the other nodes has simplified the neighborhood of those nodes, as well). If even this fails, (i.e. each remaining node takes longer than the time limit to process), it will assume that all these nodes are members of the same, huge clique (this is a reasonably safe assumption, since this is indeed the case for several networks).

Top

5.3  The View menu

After computing the communities of a network (or after loading the results of a previous community finding), CFinder can show you the results in various formats. The default view is “Communities”.

Top

View --> Vertices: View the communities of a selected vertex

In this view the list of node names appears in the lower left panel. There is a search field at the bottom of the node name list. To find a node in the list, type its name into this search field, and press ENTER. Please, make sure to type the name with the correct spelling. The text entry field auto-completes, so you can type the first few characters of the name to find the first name on the list that begins with these characters.

In the list of nodes after the name of each node the number of its communities – i.e., the number of communities that the node is contained by – is given in brackets. If the node has no communities, then there is no number. The communities of a node can have different k values (k is the clique size parameter in the community search algorithm). Select a node in the lower left panel to view in the upper left panel the list of k values of the communities containing this node.

In the upper left panel the k values of the communities of the selected node are listed. A lower k value means communities with lower link density (less stringent community search resulting in larger communities), and a higher k value means communities with higher link density (a smaller number of stronger, but more cohesive communities). In the upper left panel select one of the k values to view the communities of the selected vertex at this k value. The communities will be displayed in the lower right panel.

Communities of the protein Pex13p in the DIP “yeast core” protein-protein interaction network. (Shown with the prefuse widget.) The colored areas show the outline of the communities. Data source: Database of Interacting Proteins (DIP).

Communities of the protein Pwp2p in the DIP “yeast core” protein-protein interaction network. (Shown with the older graph widget.) The proteins Krr1p, Pwp2p and Sik1p are colored red, because they participate in more than one of the displayed communities, i.e., they are the overlaps. Data source: Database of Interacting Proteins (DIP).

Top

The graph visualization panel

You can adjust the graph displayed in the lower right panel – the graph visualization panel – in several ways. Some of them are listed in the table below. Please, check also this document about the dialog Tools > Settings (5.3.3).

Note that for large communities (above 1000 vertices) the computation of the graph’s layout may take longer. If you decide not to wait until the layout routine finishes, you can select a different vertex and k (clique size) parameter value: the previous layout calculation will be cancelled and the newly selected communities will be displayed in the graph visualization panel.

If you would like to browse through the communities of selected nodes, but you do not want to visualize them as a graph, select Tools > Settings, and uncheck the Display graph item.

CFinder contains two widgets for visualizing graphs. The default, newer, one (based on prefuse) can show an animated layout and can draw community borders. The older one is the same as the on in CFinder 1.21. To select between these two, use the use prefuse widget checkbox in the Tools --> Settings dialog.

Top

Prefuse widget

The main new features the new widget supports are the community borders and the continous, animated layout. The community borders are convex 'rubberbands' draw around the nodes of the communities. All nodes of the community will be inside this border. The overlap of these borders can show the overlap of communities visually. One note of warning: unfortunately it can not be quarranteed that other nodes, not belonging to the communities, will not be inside this area. The display of the community borders can be toggled with the 'show community borders' checkbox on the prefuse settings panel.

The layout algorithm used in the new widget can run interactively (this is the default setting), which means that the graph view is updated as the nodes are moved by the algorithm. The layout method is based on a physical model: edges are modeled as springs, with a given length and spring coefficient. There is also a global repulsion between the nodes and friction, to slow them down. The parameters that control the strength of these forces can be adjusted on the prefuse settings panel (Tools -> Prefuse settings...).

Opening a community will first place all nodes near the center of the screen, and then allow the graphs to relax according to these forces. The nodes and communities can be moved by grabbing them with the mouse. The neighbourhood of the moved object will react accordingly: for example moving a node will move its neighbors as well, following the 'edges are springs' model. Similarly adjusting the layout parameters on the prefuse settings panel will have immediate effect, as if changing the spring coefficients, etc.

The position of the nodes will be continously updated according to the physical model as long as the layout algorithm is running. This might be distracting occasionally. (For example, when most of the graph is layouted nicely, but there are small adjustments to be made, to avoid false overlaps between the communities.) In such cases the layout algorithm can be turned off either with the 'stop layout' button on the toolbar or using the 'run continous layout' checkbox on the prefuse setttings panel. With the algorithm turned off all nodes will be stationary, moving one will only move that node and none of its neighbors, etc.

The new widget uses mostly the same mouse-actions as the old one: nodes can be selected by clicking on them, moved by grabbing and dragging them with the mouse. Grabbing and dragging the background will move the whole graph, while grabbing and dragging a communitity will move only the nodes it contains.

In addition, the whole graph can be zoomed with either the mouse-button, or by clicking with the right mouse button on the background and dragging. Double-clicking with the right mouse button on the background will zoom the graph to fill the display. Severals nodes at once can be selected with a rectangle-selection using the middle mousebutton (click and drag; note that many operations, like 'communities of selected vertex' will require only one node to be selected.).

Top

View --> Communities

In this view you can have a look at the communities separately. However, if you would like to explore the connections of a community to other communities, then you can select a vertex in the graph and click on the walk button. This will bring you to the “Vertices” view where all communities of the selected node are displayed. Remember that at different k (community finding stringency) values the communities of a node can be different. If you start from a community with k=4, then pressing the walk button will bring you to the communities of the selected node at k=4.

Community no. 6 at k=4 in the DIP yeast core protein-protein interaction network.

In the left panel communities are listed by their k values (community finding stringency values). Click on one of the listed communities to view it as a graph in the lower right panel. To highlight a vertex or an edge in the graph, click on its name in the upper right panel. The cliques contained by the selected community are also listed in this panel.

Top

The Zoom and Walk buttons: Explore your network and navigate between the different views

The Zoom and Walk buttons help you to navigate between the various views. To learn what actions they will perform in your current view, just read their text labels.

You can start by looking at the communities of a selected vertex, then highlight one community (use the tabs in the upper right panel) and press the zoom button to view the graph of communities around this community. In the network of communities you can select a different community and click on the walk button to see the neighbors of that community: you are “walking” on the graph of communities and CFinder shows you the neighborhood of the selected community. After your walk on the community graph, you can select some of the communities and press zoom to view their nodes.

Top

View --> Cliques

This option lists the cliques detected by CFinder. Each clique has an index. To view the list of nodes in a clique, open the folder of the clique.

A short reminder: a clique is a complete subgraph (each node is connected to all other nodes) not contained by any other complete subgraph.

Clique view: the cliques of the DIP yeast core protein-protein interaction network are listed in the left panel.

Top

View --> Stats: Statistics of the communities.

With this option you can view the community statistics in your network for a selected k-clique size. The “log-log plot” button changes both scales to logarithmic (and back to linear), while the “cumulative distribution” button switches between the original histogram of values and the plot with 1 – P, where P is the cumulated probability density function.

Four types of statistics are available for each k-clique size:

For the visualization of the statistics, CFinder uses the Java package JFreeChart 1.0.0. To zoom in, left click inside the chart, hold down the left mouse button while moving the mouse. This way you can select the rectangular area that you would like to enlarge. To zoom out completely and to view the entire distribution, right-click inside the chart to open a menu of options, and then select Autorange à Both Axes from this menu.

To export a distribution, right-click on the distribution, select Export from the pop-up menu and enter a file name in the “Save” dialog. Currently, there is one available file format for exporting the distribution (PNG), please enter a file name ending with .png. Further information about JFreeChart can be found at the website of JFreeChart: http://www.jfree.org/jfreechart.

Statistics of the communities in the “cond-mat” collaboration network or researchers; cumulative distribution of community size, community degree, vertex membership, and community-community overlap. Data source: http://www.arXiv.org/cond-mat.

Top

View --> Graph of communities

In the graph window only a part of the community graph is displayed: the community selected in the left panel and its neighbors within a fixed distance. This fixed distance is 2 by default, and it can be changed in the Tools > Settings menu: set the “Community graph depth” variable to your preferred value.

To view the original nodes of a group of communities, select these communities and press zoom.

In the graph (network) of communities (i) nodes represent the original network’s communities and (ii) two nodes are connected, if the corresponding communities in the original graph overlap (i.e., they share at least one node).

A part of the network of communities (k=4) around community no. 40 in the DIP yeast protein-protein interaction graph. Community no. 40 and its neighbors at a maximum distance of 4 are displayed.

Top

5.4  The Tools menu

Tools --> Export graph

Exports the graph currently displayed in the graph visualization panel (in the lower right panel) into a file. A large list of formats are supported, for example BMP, EPS (Encapsulated PostScript) and PNG (Portable Network Graphics).

Top

Tools --> Stop calculation

Use this option to stop the calculation of the graph layout.

Top

Tools --> Settings

This dialog contains general settings, options for the communities and for the graph of communities.

Top

General settings

• Use prefuse widget. Select whether the graph should be drawn using the new prefuse widget (animated layout, community borders), or the old one.
• Draw graph. Select whether in the lower right panel the graph should be displayed. (The graph shows the communities of a selected vertex, a clique, a community or the network of communities.) Uncheck this option, if you would like to see only the list of nodes in a large community, but not the community as a graph.
• Highlight color. Color of the selected nodes and links in the graph.
• Draw node label and Draw node. Check these options to draw node labels and nodes.
• Node label size and Node size. The size of a node’s label and the node itself.
• Radius for selection. To select an item (node or link) in the graph, you need to click within a circle of this radius from that item.
• Edge handle size. The size of the disk at the center of a link that can help you to select and move the link.

In the Tools > Settings dialog you can modify the display properties of the graph visualization panel of CFinder.

Top

Communities

• Color of selected community. Set the color of the currently highlighted community.
• Draw overlap. Check this option to use a different color for the overlaps of communities, i.e., the nodes and links belonging to more than one community. This option is ON by default.
• Overlap color. Color of the nodes and links that belong to more than one community.

Top

Graph of communities

• Node label color, Edge color, and Node color. The color of the nodes’ labels, the links and the nodes themselves in the graph of communities.
• Community graph depth. Draw only those communities whose distance from the selected community is not larger than this distance.
• Label lines with edge weight. The weight of an edge connecting two communities is given by the number of nodes in which they overlap, i.e., the number of nodes belonging to both communities. Check this option to put a number on each link telling its weight.
• Line width shows edge weight. Check this option to allow a different width for each line. The width of the line will show the weight of the connection between the two communities (the size of their overlap).
• Nodes have the same size. If the nodes in the graph of communities are allowed to have different sizes, then the sizes will show the number of nodes (of the original network) contained by each community.
• Node size multiplier. Set the size of all nodes with this multiplier.

Top

6.  Notes

6.1  A note on the Export graph function

On some Linux platforms the Export Graph function does not work. If you encounter this problem, please contact us. We can help you with this.

Top

6.2  How to contact us

Email: CFinder@hal.elte.hu
Web and regular mail: http://CFinder.org -- select People on the left.

Thank you for using CFinder.