{'fraction_non_alphanumeric': 0.0325225851285615, 'fraction_numerical': 0.010423905489923557, 'mean_word_length': 4.766025641025641, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Improved network community structure improves function prediction

We are overwhelmed by experimental data, and need better ways to understand large interaction datasets. While clustering related nodes in such networks—known as community detection—appears a promising approach, detecting such communities is computationally difficult. Further, how to best use such community information has not been determined. Here, within the context of protein function prediction, we address both issues. First, we apply a novel method that generates improved modularity solutions than the current state of the art. Second, we develop a better method to use this community information to predict proteins' functions. We discuss when and why this community information is important. Our results should be useful for two distinct scientific communities: first, those using various cost functions to detect community structure, where our new optimization approach will improve solutions, and second, those working to extract novel functional information about individual nodes from large interaction datasets.


Simulated annealing for modularity optimization
Simulated annealing is a stochastic optimization method and considered to be slow but the most accurate 1 . In this study, we followed the implementation of previous studies 2, 3 . Initially, a simulation is started from high temperature, T, to sample "wider" region and avoid trapping in local-maxima. As the simulation proceeds, T is slowly cooled down to focus on sampling high modularity region. At a given T, a set of movements including N 2 single-node moves and N collective moves consisting of random merges and splits of communities, are carried out 3 . For each trial movement, if Q increases, the movement is accepted, or it is accepted with probability: . After a set of movements are tried, T is cooled down to αT, where α=0.995.
Pseudo-code for the CSA optimization

Network construction
Three biological networks, metabolic networks of T. pallidum and E. coli and PPI network of S. cerevisiae, are used to investigate the relationship between modularity and quality of community structures. Metabolic network of T. pallidum was constructed from the data downloaded from KEGG (Kyoto Encyclopedia of Genes and Genomes) database 9 . A list of enzymes was obtained from 'genome' database of KEGG and related reactions are found from 'ligand' database. Reactants and products are represented as nodes and if two compounds are involved in the same reaction, they are considered to be connected. For E. coli metabolic and S. cerevisiae PPI networks, we used the same networks of the previous study 10 . The metabolic network is obtained from E. coli K-12 MG1655 strain (iAF1260), which is one of the most elaborate metabolic network reconstructions currently available 11 . All compounds involved in a certain reaction are connected to each other. The PPI network is generated from all available protein-protein interaction data of S. cerevisiae: yeast two-hybrid (Y2H), affinity purification followed by mass spectrometry (AP/MS) and literature-curated (LC) 12 . For all networks, we used only the largest component of each network.

Protein function prediction by Random Forest
For each node i, we consider each function f from its neighbors as a candidate function, and we want to design a machine to decide the adequacy of f. For each i, we calculate 11 features, 5 using only neighbor information, 5 by combining community information with the neighbor information and one background information, a fraction of proteins with function f. Applying CSA to finding overlapping communities To demonstrate the generality of our method, we implemented the objective function to detect overlapping communities introduced in the paper by Shen et al. 13 , and compared the optimization results on a word association network 14 , which consists of 7207 nodes and 31785 edges; the result is shown below. The advantages of MCL are 1) it is fast even with large networks and 2) it is easy to implement. Drawbacks of MCL are 1) it tends to detect small and dense clusters and 2) its result is sensitive to the inflation parameter, which makes it difficult to select the optimal community structure.
To compare our method with MCL, we performed the MCL clustering with the yeast PPI network used in this study. The result is shown in Figure S3. Each disconnected network represents each community detected by MCL. As shown in the figure, MCL generates a lot of small communities where P-value calculation is not meaningful. More than half of the nodes, 1574 out of 2729, are included in small communities containing less than 6 nodes.
Many graph-clustering algorithms do not work well with sparse networks as reported in a recent benchmark paper 16 . It is reported that, for sparse networks, SpectralMod (based on modularity) works relatively better than graph-clustering methods. Therefore, though the modularity may not be the best measure for community detection, utilizing it leads to a reasonably good result for sparse networks to help function prediction. Computational complexity of CSA and SA Due to the stochastic nature of CSA algorithm, it is hard to obtain an analytic estimate of the computational complexity of the algorithm. Therefore we empirically estimated the computational complexities of CSA and SA from a set of benchmark data 17 . The results show that the complexity of CSA scales as O(n 2.6 ) , which is comparable to that of MCL without approximation, O(n 3 ) , and better than that of SA, O(n 4.3 ) , where n is the number of nodes. Practically, MCL is implemented with a pruning scheme, which reduces its complexity to O(nk 2 ) , where k is much smaller than n in general, which makes it applicable to large networks.
Although CSA may not be as efficient as MCL for large networks, there are two ways to improve the efficiency: 1) the use of fast heuristic method for local Q maximization and 2) with the help of parallel computing. In this work, we used a stochastic quench method, SA at T=0, for local Q maximization, which is slow but allows us to explore a solution space more thoroughly. Replacing this procedure with a fast heuristic method will enable CSA to be applicable to large networks. Unlike the SA method, CSA can be implemented in a parallel way, which makes it applicable to large networks that are inaccessible by SA.

Figure 11 Precision--Recall curve of predictions of cellular component GO terms based on the yeast PPI network using a) RF-comm with community from CSA (red plus), b) RF--comm with community from SA (blue x--mark), c) RF--local (green circles), d)
Markovian random field (cyan square) and e) Majority voting (magenta diamond) methods.

Figure 12 Precision--Recall curve of predictions of molecular function GO terms based on the yeast PPI network using a) RF-comm with community from CSA (red plus), b) RF--comm with community from SA (blue x--mark), c) RF--local (green circles), d) Markovian random field (cyan square) and e) Majority voting (magenta diamond) methods.
Representative examples of consistent function predictions of unannotated proteins in PPI network of S. cerevisiae.