{'fraction_non_alphanumeric': 0.032544777124388385, 'fraction_numerical': 0.008798312160524308, 'mean_word_length': 4.302904070459414, 'pattern_counts': {'":': 0, '<': 8, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Finding HeavyPaths in Weighted Graphs and a Case-Study on Community Detection

A heavy path in a weighted graph represents a notion of connectivity and ordering that goes beyond two nodes. The heaviest path of length l in the graph, simply means a sequence of nodes with edges between them, such that the sum of edge weights is maximum among all paths of length l. It is trivial to state the heaviest edge in the graph is the heaviest path of length 1, that represents a heavy connection between (any) two existing nodes. This can be generalized in many different ways for more than two nodes, one of which is finding the heavy weight paths in the graph. In an influence network, this represents a highway for spreading information from a node to one of its indirect neighbors at distance l. Moreover, a heavy path implies an ordering of nodes. For instance, we can discover which ordering of songs (tourist spots) on a playlist (travel itinerary) is more pleasant to a user or a group of users who enjoy all songs (tourist spots) on the playlist (itinerary). This can also serve as a hard optimization problem, maximizing different types of quantities of a path such as score, flow, probability or surprise, defined as edge weight. Therefore, if one can solve the Heavy Path Problem (HPP) efficiently, they can as well use HPP for modeling and reduce other complex problems to it.


INTRODUCTION
Graphs are convenient data structures for modeling real life data such as social networks, citation networks, the web, phone call and email histories, purchase/transaction records and user actions [1]. It is easy to model data with graphs. However, we need sophisticated tools to make sense of such data. In order to do so, we need to study notions such as connectivity [1], centrality [6] and density [28]. Graph algorithms are at the core of community detection, for discovering various types of groups based on previous interactions of individuals [39]. Random walk based methods have been used in many mining and graph applications. Mining interesting multi-relational patterns is solved as discovering maximal pseudo cliques in k-partite graphs [41].
A problem that has received relatively less attention in the research community is that of finding k cycle-free heaviest paths of length in a weighted graph (HPP). Sum and product are examples of monotone aggregation functions that define the aggregate weight of a path. Generating lists of items of interest is a great practical example. Suppose edge probability w (u,v) = P (v|u), the conditional transition probability that a random user would like to listen to u (as next song) given that v is the current song. Also assume there is equal probability for any user to like any song. Using product as aggregation function, the weight of a path is directly proportional to the probability that a cycle free "chain" of songs appears one after another in a listening session. A heavy path in such graph, represents a playlist with high overall transition probability between songs. The graph can be created according to user(s) listening history. We can imagine other kinds of lists such as reading lists of books or papers that show flows of ideas through publications.
In influence networks, recently there have been attempts for sparcification [42]. A path with high probability is a highway for spreading influence in an influence network with transition probabilities on edges. A more principled approach takes into account only heavy paths rather than technicalities and complex problem definitions. A complete study of all of HPP applications goes beyond the scope of this paper. We need the preliminary work done in this paper, in order to aim at creating a toolbox that uses heavy paths for network analysis. Here, we show a possible novel application for community detection in research communities in a co-authorship network. We use maximal frequent sub-paths in top-k heavy paths in order to discover the cores and further "grow" each core with peripheral nodes using existing edges in top paths. We enhance our observations with metadata, and show that the core communities found using our approach unanimously report highly influential researchers.
We make the following contributions in the subsequent sections: • We formalize and motivate the HPP problem and show it is NP-hard and inapproximable. We discuss four exact algorithms, and provide a comparison of classical vs. novel algorithms for solving HPP. We provide a comprehensive experimental study of HPP algorithms presented in Section 7.
• We present a case study to discover small but influential networks of people in research communities. We do this analysis on a sub-graph of DBLP co-authorship graph, and report the results in Section 6.
• We show how a well studied top-k query processing problem in the database literature can be converted to HPP on graphs where there is no database. We solely focus on algorithmic aspects, and propose a more scalable algorithm that overcomes the shortcommings of the Rankjoin [25] algorithm.

TECHNICAL PROBLEM DEFINITION
The most similar well studied problem to HPP in the literature is finding top-k heavy paths on directed -partite graphs. A nice example is k -Stable Clusters problem [7]. Absence of cycles makes the studied problem considerably simpler than HPP. Furthermore, practical applications of HPP are not limited to -partite graphs as described in Section 1. We show HPP is NP-hard and propose a practical algorithmic framework for solving it in the general case. It is common to use exponential time but efficient algorithms for mining purposes. Great examples are Apriori and FP-Growth [43], that is used for frequent item-set mining. Heavy paths also represent lists of highly connected items that can be used in similar ways to frequent item-sets and also for ordering of the items in the set.
Given a weighted graph G(V, E, W ), where weight w (u,v) represents the edge weight between u and v, we aim at finding the k heaviest simple paths of length , with highest overall path weights. We call this the Heavy Path Problem (HPP).
A simple path of length is a sequence of nodes (v0, . . . , v ) such that (vi, vi+1) ∈ E, 0 ≤ i < , and there are no cycles, i.e., the nodes vi are distinct. Unless otherwise specified, in the rest of the paper, we use the term path to mean simple path. We focus on sum and product, as aggregation functions that define the weight of a path. For simplicity of presentation and practical considerations, we present using sum. We define weight of P = (v0, ..., v ), as P.weight = −1 j=0 w (j,j+1) . Furthermore, we know we can convert product to sum using log values and this does not change the order of the list of top-k heaviest paths.
Finding the heaviest path for a given parameter is equivalent to the -TSP problem, defined as follows: Given a weighted graph, find a path of minimum weight that passes through any + 1 nodes. It is easy to see that for a given length , a path P is a solution to -TSP iff it is a solution to HPP (with k = 1) on the same graph but with edge weights modified as follows: let w (u,v) be the weight of an edge (u, v) in the -TSP instance; then the edge weight in the HPP instance is w (u,v) = C − w (u,v) , where C is any constant. This reduction works in both ways given that we use the same constant C. We are not concerned with negative edge weights since we deal with paths without cycles; but, we focus on cases where edges are either all negative or all positive for simplicity. It is well known that -TSP is NP-hard (as a version of TSP). Furthermore, -TSP does not have any bounded approximation in the general case i.e. no triangle inequality on edge weights etc [2,3]. Proof. We know -TSP is not approximable. Remember the C−w reduction between -TSP(G1) and HPP (G2) introduced earlier. Suppose C = 0 and k = 1, if P is the answer to HPP (the heaviest path) on G2, it is the answer to -TSP on G1 after −w transformation on edge weights. The weight of P in G1 (−Wmax) is the negative of its weight in G2 (Wmax). If we find an α (0 < α < 1) approximation to P on G2 as a result of finding path Q in polynomial time we have Q.W ≥ α × Wmax. On G1 graph equivalently we can say, −Q.W ≤ α × −Wmax. Since −Wmax is the optimal answer on G1 graph (i.e. minimum weight among all paths), it is guaranteed that −Q.W is in the range −Wmax ≤ −Q.W ≤ α × −Wmax and is a true approximate answer to -TSP. We know -TSP is not approximable. According to the above argument, approximability of HPP results in approximability of -TSP. This is in contradiction with the known fact that -TSP and TSP are not approximable in the general case.
In Figure 1(a), the heaviest simple path of length 4, is obtained by visiting the nodes in the order 6-1-2-3-4 and has a weight of 3.35. In contrast, a different permutation of the nodes 4-3-6-1-2 has a weight of 3.08. The higher weight of a path can represent a sequence with more strength or better quality. Different permutations result in paths with different weights simply because paths consist of different edges most likely with different edge weights.

Baselines
An obvious algorithm for finding the heaviest paths of length is performing a depth-first search (DFS) from each node, with the search limited to a depth of , while maintaining the k heaviest paths and avoiding cycles. This is an exhaustive algorithm and is not expected to scale. A somewhat better approach is dynamic programming. Held and Karp [36] proposed a dynamic programming algorithm for TSP which we adapt to HPP as follows. Since path lengths required in our problem are typically much smaller than the total number of nodes in the graph, we replace the notion of "allowed nodes" with "avoiding nodes". The idea is to find the heaviest J-avoiding path of length − 1 that ends in one of the neighbors of J. We can repeat this recursively during the execution using smaller path lengths and larger avoidance sets as parameters. The base case is where the input parameter assigned to length is 1, in which we only need to consider the paths created by extending the current path by one hop, making sure we do not extend by any nodes that belong to the ( − 1) size avoidance set. The rest is similar to DFS. We repeat this for every node(J) and keep track of the heaviest path. Dynamic Programming algorithm aggregates and discards many short path segments early on by choosing the heaviest one that ends at a certain node. Both DFS and Dynamic Programming can be easily generalized to report top-k paths which is not the focus of this paper.

Sorted Access Algorithm (SAA) for HPP
The methods discussed in the previous section lack the ability to prune the search space using edge weights. It may be more promising to first look at those parts of the graph with heavier edge weights. If they connect, they can create heavy paths. This way, we solve HPP only for a smaller sub-graph or at least explore the search space more efficiently. This can make a considerable difference to the exponentially increasing running time of the problem using smaller input size. There exists a body of work on top-k algorithms in the database community started by Fagin et al. [34]. These algorithms aim at finding top-k items without searching the whole search space using sorted access. The framework is such that partial item scores from multiple sorted lists (l1...l ), are aggregated using a monotone aggregation function. Following their idea more aggressive top-k algorithms were proposed in order to extend their framework with probabilistic guarantees such as [29]. We can argue the weight of a path (item), is the aggregation of several partial item scores (edges). This makes following top-k query processing ideas promising for solving HPP. In particular, in Rank Join [26,4] problem, partial scores in l1 can join more than one partial scores in l2. For instance, suppose l1 provides a sorted list of movie theaters and l2 provides a sorted list of restaurants sorted by their popularity score. One may be interested in watching a movie and going to a restaurant in the same neighborhood. The score of a combination is defined using the sum of the individual scores and items of interest are (movie theater, restaurant) combinations. There may be many movie theaters and restaurants in the same neighborhood.
Problem Conversion: Define a tripartite graph. The first column of nodes is a single dummy node (dummy1) as well as the third column(dummy3). Every node in the middle column represents a neighborhood (such as downtown). Every movie theater (l1), is modeled as an edge that con-nects dummy1 to its neighborhood with a directed edge. Every restaurant (l2), is modeled as a directed edge that connects its neighborhood to dummy3. Edge weight is defined as item score. Heaviest paths of length 2 are top combinations. Rankjoin can be converted to heavy path on a tripartite graph.
We design an adaptation of Rankjoin that works with selfjoins (i.e. all li are identical) for solving HPP on general graphs. Direct usage of Rankjoin results in creating many paths with cycles that need to be pruned later on. SAA (Algorithm 1), avoids creating cycles early on. SAA algo- It extends all paths of length i in P i with matching edges in ScannedEdges (i.e. smaller search space) and ensures no cycles are created. This results in paths of length i + 1. In case P i+1 is empty because there are no matching nodes to join without cycles, naturally, no path will be created. For instance no path of length l > 1 is created after joining the heaviest edge and the empty set of scanned edges. This is how Join is defined as an operation. Join is one of the operations defined in Relational Algebra. Therefore, it is not scary to use Join, it has been used in practice as part of the DBMS operations for a long time. We do an enhanced implementation for self-joins that prunes cycles as well. Paths of length will be created after enough edges are scanned in sorted order. This operation is repeated − 1 times, until all possible paths of length including e and heavier edges are produced. At this point (line 10), SAA knows that no path can be created during the rest of execution which is heavier than θ = e.w + ( − 1) × Wmax. Therefore, if we have already constructed k paths heavier than θ, we know that these are the correct top-k paths of length . In order to speed up the Join operation, ScannedEdges is maintained as a hash table that maps nodes (keys) to edges (values). Consider the example graph in Figure 1(a). Suppose we are interested in the heaviest path of length 3. The SAA algorithm proceeds by scanning the edge list in sorted order of the edge weights. After reading 4 edges at depth d = 4, the edge weight (w4) is 0.77 and wmax = 0.93. We can calculate the threshold (upperbound) as: θ(2.63) = 0.77 + (3 − 1) * 0.93. At depth 5, SAA is able to construct the path (6,1,2,3) and θ(2.62) = 0.76 + 2 * 0.93. Since θ is equal to the weight of (6,1,2,3), we know it is at least one of the heaviest paths in the graph and can terminate without processing the rest of the edges in the sorted list. This is what we call search space pruning by Sorted Access.

LIMITATIONS OF SAA AND OPTIMIZA-TIONS
LIMITATION 1. Let P be a path of length and suppose e is the lightest edge on P , i.e., its weight is the least among all edges in P . Then until e is seen under sorted access, the path P will not be constructed by SAA.
Limitation 1, simply follows the fact that paths are created using only sorted access to the list of edges. If we run SAA on the graph of Fig. 2, we won't create the heaviest path (a,b,c,d) until the edge (c,d) is scanned. However, (c,d) is the lightest edge in the graph. This means following only sorted access, may delay the construction of the heaviest path until many irrelevant paths are created and discarded. This observation motivates the following optimization for finding heaviest paths. OPTIMIZATION 1. We should try to avoid delaying the production of a heavy path of a certain length until the lightest edge on the path is seen under sorted access. One possible way of making this happen is via random access. However, random accesses have to be done with care in order to keep the overhead low.
In the example of Fig. 2, suppose we have constructed (a,b,c) and know it is the heaviest path of length 2. It may be a good heuristic to extend (a,b,c) with new edges such as (c,d) and create paths of length 3. Since (a,b,c) is the heaviest path of length 2, it is very likely to create heavy paths of length 3 by extending (a,b,c). Making access to graph edges such as (c,d), regardless of where they appear on the sorted list of edges, is what we refer to as "random access". An example of random access is presented by Figure 1(b). Making random access to the edge list simply means reading an edge without caring about where the edge is located on the sorted list of edges (through the adjacency matrix). This can help produce heavy paths containing low weight edges earlier. Our case study in Section 6, shows one practical example where a low weight edge on a heavy path, can have a meaningful interpretation. The discussion is provided in Section 6, for Gui-Rong Xue's edges with others. Following this optimization, suppose we use random accesses to find "matching" edges with which to extend heaviest paths of length − 1 to length . This way we won't delay the creation of heavy paths until their lightest edge is visited under sorted access. However, this may not be enough for early termination of the algorithm. Another decisive factor in early termination is the upperbound threshold (θ) value on weight of paths we have not created yet using the ScannedEdges. SAA stops when θ gets smaller than the weight of the heaviest path of length discovered so far. Suppose there is an instance in which the heaviest path of length is lighter than wmin + ( − 1) × wmax. In this case, SAA will produce every path of length before reporting the heaviest path, resulting in no pruning. In Fig. 1(a), this happens when trying to find the heaviest path of length 4 and in Fig. 2, when trying to find the heaviest path of length 3. The following lemma highlights a natural possibility during the execution of SAA for obtaining a tighter threshold that results in earlier termination. LEMMA 1. Let P be the heaviest path of length . When SAA terminates, every path of length − 1 that has weight no less than P.weight − wmax, will be created. This includes the heaviest path of length − 1.
Proof. Suppose SAA finds P at depth d. This means P.weight ≥ Notice that P.weight − wmax is a lower bound on the weight of the heaviest path of length − 1. Therefore, if there is a path of length − 1 that is heavier than P.weight − wmax, it will be produced by SAA by depth d.
One way of making the threshold tighter is by keeping track of shorter paths. For example, if we know P is a heaviest path of length − 1, we can infer that the heaviest path of length cannot be heavier than P.weight + wmax, a bound often much tighter than w d + ( − 1)wmax.
For this, we need to keep track of the heaviest paths of length − 1 one by one to lower the threshold more aggressively, gradually and smoothly. Pursuing this idea recursively leads to a framework where we maintain and release heaviest paths of each length i, 2 ≤ i ≤ , at the right time and make the next threshold tighter. More precisely, we can perform the following optimization. For this purpose, we can use Buffers as sorted sets (priority queue) in order to store (insert) and release heavy paths (remove top). Figure 3 schematically describes the idea of using buffers for different path lengths. Buffer B1 is the sorted edge list for the graph in Figure 2. Buffers B2 and B3 store paths of length 2 and 3 respectively. When random accesses are performed to extend paths of length l − 1 to those of length l, the buffers can be used to store these intermediate paths.  For instance, when the heaviest path of length 1 is seen, say edge (a, b) is seen, it can be extended to paths of length 2 by accessing edges connected to its end points, as represented by B2 in Figure 3. Similarly, the heaviest path of length 2 can be extended by an edge using random access to obtain path(s) in buffer B3. Obviously, we do not extend all shorter path segments and extend only the one that is known to be the next heaviest path of shorter length in its own buffer. We describe this framework in more detail when we present the final algorithm next.

REPEATED SORTED ACCESS(RSA) AL-GORITHM
We start this section by providing an outline of our main algorithm for solving HPP. Our algorithm maintains a buffer Bi for storing paths of length i explored and not released (P.w < θ), where 2 ≤ i ≤ . Let threshold θi denote an upper bound on the weight of any path of length i that has never been inserted into Bi. Algorithm 2 describes the overall approach. It takes as input a list of edges E sorted in non-increasing order of edge weights, and parameters and k. It calls the NextHeavyPath method (Algorithm 3) repeatedly until the top-k heaviest paths of length are found.

Algorithm 3 NextHeavyPath (E, l)
Input: Sorted list of edges E, and path length l Output: Next heaviest path of length l 1: if l = 1 then 2: P 1 ← ReadEdge(E) 3: θ2 = 2 × P 1 .weight 4: return P 1 5: while B l .topScore ≤ θ l do 6: P l−1 ← NextHeavyPath (E, l − 1) // recursion 7: s, t ← EndNodes(P l−1 ) 8: for all y ∈ V | (y, s) ∈ E do 9: B l ← B l ∪ ((y, s) + P l−1 ) // avoiding cycles 10: for all z ∈ V | (t, z) ∈ E do 11: B l ← B l ∪ (P l−1 + (t, z)) // avoiding cycles 12: P l ← RemoveTopPath(B l ) 13: if l < then 14: θ l+1 = max(B l .topScore, θ l ) + wmax 15: return P l Algorithm 3 1 describes the NextHeavyPath method. It takes as input a list of edges E sorted in non-increasing order of edge weights, and the desired path length l, l ≥ 2. It is a recursive algorithm that produces heaviest paths of shorter lengths on demand, and extends them with edges to produce paths of length . The base case for this recursion is when l = 1 and the algorithm reads the next edge from the sorted list of edges. The ReadEdge method returns the heaviest unseen edge in E (sorted access, line 2). If l < , the path of length l obtained as a result of the recursion is extended by one hop to produce paths of length l + 1. Specifically, a path of length l < is extended using edges (random access, lines 8 and 10) that can be appended to either one of its ends (returned by method EndNodes). The "+" operator for appending an edge to a path is defined in a way that guarantees no cycles are created. The threshold θ l is updated aggressively when the next heaviest path of length l − 1 is released from B l−1 . This is done by calling the method RemoveTopPath for buffer B l−1 and returning the resulting path. If there is no path already in the buffer that beats θ l−1 , this results in more recursion using smaller l, until this condition becomes true at some point during the execution. At any point during the execution if i < and the next heaviest path of length i (P) has been obtained (Bi.topScore > θi), θi+1 is more intuitively updated as θi+1 = P.W + Wmax 2 . THEOREM 1. Algorithm RSA correctly finds top-k heaviest paths of length .
Proof. The proof is by induction. The base case is for going from edges to paths of length 2. Given that all of the edges above depth d are extended, the heaviest path that can be created from them is already in B2. The weight of the heaviest path that can be created from lighter edges is at most 2 × w d . If the heaviest path in B2 is heavier than 2 × w d , then it must be the heaviest path of length 2. Assuming the heaviest paths of length l are produced correctly in sorted order, we show the heaviest path of length l + 1 is found correctly. Suppose P , the heaviest path of length l + 1, is created for the first time by extending Q, which is the n th heaviest path of length l. The next heaviest path of length l is either already in B l or has not been created yet. Therefore, max(θ l , B l .topScore) is an upper bound on the next heaviest path of length l that has not been identified yet. Any such path can be extended by an edge of weight at most wmax. Suppose when the m th heaviest path of length l is seen, max(θ l , B l .topScore) + wmax is updated to a value smaller than P.weight. It is guaranteed that P is already in B l+1 and has the highest weight in that buffer. In other words, when the threshold  is smaller than P.weight, the difference between the weight of P and next heaviest path of length l is more than wmax. Now, paths of length l + 1 that can be created from heavier paths of length l are already in the buffer, and no unseen path of length l can be extended to create a path heavier than P . Therefore, P is guaranteed to be the heaviest path. The preceding arguments hold for top-k heaviest paths where k > 1.

COMMUNITY DETECTION CASE-STUDY
Suppose we have a co-authorship graph that connects researchers according to their publications. The edge weight is defined as the sum of "pairwise collaboration credits" that researchers get from each paper they publish together. Pairwise collaboration credit for a pair of authors in a paper, is 1/authorN um. Where authorN um is the number of authors of a paper. Given a collection of publications, we define an edge between two researchers if they have published at least one paper together. Then use the sum of "pairwise collaboration credits" they get from all of the papers they have published together as the edge weight. Single author papers do not contribute to edge weights. We further normalize edge weights by the maximum so that they are all in [0, 1]. Using this graph, and given parameters and k and a popularity 3 parameter, we do the following, 1. Find top-k heaviest paths of length l 3 Same as support in frequent pattern mining 2. Finding cores of communities: Find all maximal frequent sub-paths in top-k paths. Frequent sub-paths are those that appear in more number of paths than the popularity parameter.

Aggregate top-k paths and form the aggregate graph of top paths
4. Given a core and the aggregate graph of top paths, do the following: add any edges that connect any other researchers in the aggregate graph of top paths to the core. This shapes a community of core researchers that appear on many heavy paths. It also adds those other researchers who are strongly connected to the core community.
5. Communities can grow using larger values for k that adds more nodes to the picture. In a way, k can be used to zoom in and zoom out of communities.
Using DBLP data [27], we constructed this graph using papers published between 2008 and 2011 (inclusive), presented in the main program one of these conferences: "SDM", "PKDD", "ICDM", "SIGKDD", "CIKM", "SIGIR", "ICML", "NIPS", "WWW" and "WSDM". Figure 4, shows two of the communities we find using parameters l = 5, k = 100 and popularity = 10. We provide this graph (DBLPG), and the top-100 paths of length 5, to enable the reader to reproduce the communities described 4 . We notice that the core of community 1 (Figure 4(a)) contains the pair of researchers with the highest edge weight in the graph. This shows a long lasting collaboration. We did a quick google search about each of the core communities in DBLPG. Irwin King and Michael R. Lyu work for the Chinese University of Hong Kong. They are connected to Gui-Rong Xue who is the senior director at Aliyun.com and he is connected to a principal researcher from Microsoft research Asia (Zheng Chen).
Most of the researchers in community 2 (Figure 4(a)) have worked for Yahoo! Research Labs, including the three researchers in the core. Andrei Z. Broder is currently a distinguished scientist at Google. He has previously worked at Yahoo!, IBM and Altavista. We also found on his Wikipedia page that he is the inventor of MinHash locality sensitive hashing. Evgeniy Gabrilovich, is a senior staff research scientist at Google who also used to have a central role at Yahoo! research. Vanja Josifovski apparently still works for Yahoo! and is a Principal Research Scientist and the Lead of the Performance Advertising Group at Yahoo! Research. Most of the other researchers in community 2 work for yahoo! as their emails appear on their publications. Some may have moved to Google recently! It is worth noting that we discovered three other cores as well in our output. Due to space limitations, we only report the cores: core 3 = {Andrei Z. Broder, Evgeniy Gabrilovich, Xuerui Wang }(weight = 0.73), core 4 = {Shuicheng Yan, Ning Liu, Jun Yan, Zheng Chen } and core 5 = {Ning Liu, Jun Yan, Zheng Chen, Weizhu Chen }. Xuerui Wang is also a scientist at Yahoo! labs. Cores 4 and 5 have size 4. We notice that a sub-path of length 3 is shared between these two, with all researchers from Microsoft Research Asia. Community 1 is connected to two of these three researchers through Gui-Rong Xue. This shows a potential for collaboration between these two cores in the future! who are the Chinese University of Hong Kong and Microsoft Research Asia. Changing the parameters l, k and popularity, changes the output in the form presented in Figure 6. It can also help with creating a visualization tool that adapts its output with the current parameter values and be used for visualizing hierarchies and relationships of communities at different scales. Such a tool needs to run RSA repeatedly with different parameter values in order to change its view. This highlights the importance of scalability and efficiency for HPP problem. We leave the continuation and implementation of this idea to our future work.
The case study presented in this section, is also an example of an application where finding the exact solution is required. This is because we focus on 100 heaviest paths and frequent pattern mining in order to discover the cores of communities. Heuristic or any sort of approximate solutions may result in paths that do not necessarily go through the cores that form the top communities. Top-k heaviest paths, rely on their cores to be heavy!

Reproducibility
We use four graphs in our experiments. We create graphs using Cora 5 , last.fm 6 and DBLP datasets. Cora(70 nodes-1580 edges): nodes represent research topics and edge weights are defined using the average fraction of citations between the two topics. Last.fm(40k nodes-183k edges): we crawled the existing collection of playlists. Nodes represent songs and edges represent co-occurrence in playlists. Edge weight is defined using the Dice coefficient 7 . BAY(321k nodes-400k edges): it represents the road network in San Francisco Bay area 8 . For this graph we perform the C − W (C=1) transformation described in Section 2, and solve -TSP because distance minimization makes more sense for road networks. DBLPG(4.5k nodes-9k edges): Section 6 describes how the graph is created. In all cases, the graph we work with has edge weights in [0 − 1] and the input graph is a text file that stores one edge per line in this format: "source destination weight". You can access a .zip file containing all the preprocessed graphs 9 . We do not use graphs with millions of edges since the problem is NP-hard and we focus on finding exact answers. On the other hand, all of the graphs we use in experiments deal with practical real life applications. One interesting fact we discovered in our experiments is that the smallest of the graphs (Cora) we use, is one of the most challenging scenarios. This is due to the fact that its average node degree is higher than others and this results in an exponentially larger number of longer paths when increases. We do not report any results regarding the DFS algorithm because it is inferior to Dynamic Programing in all cases. Source code of all algorithms, along with instructions for running can be downloaded 10 . All experiments were performed on a Linux machine with 64GB of main memory and 2.93GHz-8Mb Cache CPU. To be consistent, we allocated 12GB of memory for each run. In all of the cases where RSA 11 runs out of memory, other algorithms either also run out of the 12GB allocated memory, or do not terminate after running for a couple of days. Our implementation is in Java. For all algorithms other than RSA, we provide implementation such that the time spent on Garbage Collection can be measured accurately using the Jstat tool 12 . All of the figures that present running time use log scale on Y-axis. We further analyzed GC time and found it is negligible compared to the total running time in all cases as supposed to be since Java is one of the most reliable programming languages. Figure 5(a-c) show the running time for finding the top-1 path of various lengths for Cora, last.fm and Bay graphs. Average node degree plays a key role in the empirical hardness of HPP. This is due to the fact that the complexity of the problem increases exponentially with node degree.

Empirical Evaluation
The running time increases with for all algorithms, as supposed to be. SAA does not manage to go beyond short path lengths in most cases, the reasons being those limitations mentioned in Section 4. Beyond some depth down the sorted edge list, SAA becomes inefficient due to the increasing complexity of the problem and the fact that it either does not manage to construct heavy paths early on or the fact that the threshold decays slowly. For shorter path lengths SAA terminates earlier than Dynamic Programing because it does pruning and uses a threshold for termination while Dynamic Programing explores a larger search space. RSA performs considerably more efficient than other algorithms except for one case on Cora graph for = 3 where it is slightly less efficient than SAA. We believe this is due to the fact that RSA uses a combination of sorted and random access. Random access results in fundamental improvements in the running time as we see in most cases. However, in some rare cases SAA may get lucky because it avoids random access and also the edge weights are such that result in fast termination. Albeit, at the cost of losing all the other experiments. All in all, our findings show that RSA is a way more scalable and reliable algorithm. Dynamic Programing behaves consistently and manages to achieve pruning by aggregating shorter path segments early on. However, it finds the heaviest path ending at every node and although it scales to longer lengths, it is orders of magnitude slower than RSA. We would like to highlight again that we use log scale on Yaxis and the difference in the running times is considerable. All in all, there is no question about the surprising scalability of RSA in all experiments. Figures 5(d-f), compare the running times of SAA and RSA for varying k and fixed = 4, since these two are the algorithms designed to work as top-k algorithms. In all cases, RSA is more efficient and it spends a smaller marginal running time compared to SAA for finding top-k. We observe sudden jumps in the running time of SAA when k changes while RSA continues to work reliably for values of k less than 100 in these experiments and scales more smoothly. 11 We use the name HeavyPath for our implementation of the algorithm. 12 Java does garbage collection automatically using GC algorithms.
http://docs.oracle.com/javase/1.5.0/docs/tooldocs/share/jstat.html We further compare the number of edge reads of SAA and RSA in Figure 6, that is a system independent notion of the running time. We observe patterns very similar to Figures 5(a-c). This highlights the fact that the number of edges read during the execution is the main factor determining the running time. We observe in some cases (for small ), SAA reads fewer edges but spends slightly more time for execution. This is due to the fact that RSA is performing random access using the adjacency matrix of the graph to construct longer paths. However, SAA performs the Join operation and looks up edges in a hash table which itself requires few milliseconds of time overall. Finally, Figure 7 shows the running times and the number of edge reads on the DBLPG graph for finding the heaviest paths of different lengths. We notice on this Graph, SAA algorithm performs more poorly compared with the Dynamic Programming algorithm. Of course, RSA beats all algorithms in all cases and finds the exact solution almost 10 times faster than the rest. Figures 7(b) and 8, illustrate this.

DISCUSSIONS
Our theoretical results prove that HPP is np-hard and inapproximable in the general case. While it makes sense to seek more tractable problem definitions by adding constraints, still we show experimentally that we can achieve scalability practical enough for our main algorithm to be used in a real time fashion and be used in smart software technologies. We use a branch and bound solution for finding the exact solution, inspired by top-k algorithms. We use a constraint , on edge weights and this makes our comparison for finding heavy paths, representing significantly important sequences in the graph more fair. Comparing path weights of paths with different lengths may not make enough sense in the general case. We show exact solution even for small , if obtained, can be used in practice effectively, while other algorithms fail to report even for small in a timely manner. It is obviously nice to scale to longer paths and this requires smarter strategies for reducing θ during the execution that leads to faster search space pruning. We make a proposal for designing a network visualization tool-box with zoom-in and zoom-out functionalities with changing k. We find our presented case study practical but obviously as mentioned in Section 1, applications are not restricted to this and there are other applications such as those in bioinformatics. We can use high probability sequences in order to fix technology related errors such as replacing inaccurate or suspicious entries or filling in missing values in biological sequences. We  can also use these high probability sequences for feature extraction from DNA which is an extremely long sequence of symbols in bioinformatics for classification and other learning tasks. One reason we choose visualizing bibliographic networks is presenting interpretable results for computer science audience. While there is a variety of solutions to be used in these applications, we want to propose a solution to a well-defined problem in computer science similar to TSP, that can be significantly leveraged for creating technologies in software industry. Another way to add constraints to the problem and make pruning more possible is through designing reliable heuristic algorithms with constraints on the distribution of edge weights. Of course, this requires careful testing for estimating distributions and we can focus on this extension in the future.
Recently, there have been advancements in the field of social networks described as Egonetworks 13 . Egonetworks are typically presented as groups of people involved in different "circles". Our bibliographic network described in Section 6, is similar to the notion of circles in Egonetwork where each list of authors represents a circle. In an extreme scenario there may be many nodes involved in each circle in domains 13 http://snap.stanford.edu/data/index.html such as concrete social networks. Any problem definition for discovering dense or significant subgraphs according to such networks can result in finding significant sub-structures. We propose an effective approach for constructing such a graph. Based on the data available we prefer to make no judgement about the significance of individuals. Our proposed solution based on finding top-k heavy paths is proven to be scalable by experiments. On the other hands we can manage to change the output using simple parameters such as k, that enables us to zoom-in and zoom-out. Our argument for reliability of our output is the following observation. We notice many heavy paths share the same exact shorter sub-paths. This emphasizes the importance of some collaborations in the bibliographic network around which an important and successful research community is formed. This led to our definition of community detection approach that makes use of maximal frequent subpaths for discovering such frequent short paths shared among many top-k heavy paths. We follow the same approach for constructing graphs from Facebook and Twitter Egonetworks. In particular, we only use circles and convert mutual presence of nodes in circles to define edges. We find the same exact method described in Section 6, in order to define edge weights. Figure 8, reports the heaviest path weights of = 1 to = 5, and compares them with those obtained from DBLP data. We use the union of all circles first and then construct the graph. Since edge weights are all scaled to (0 − 1), we expect heaviest paths of different length to be in the same range for all datasets. In comparison, we notice in Figure 9, that all graphs follow a similar curve for increasing . We notice that the slope decreases with , and it is quite likely path weight converges quickly for large . This increases the chances of finding reliable heuristic algorithms with output close enough to the exact answer of the np-hard problem. Facebook and Twitter datasets result in paths with slightly heavier weights and we believe this is because in real life networks people with strong connections belong to many active networks while researchers may not be as socially active as ordinary people. Although the difference in path weights is small and almost negligible. The most notable facts to highlight are the similar shape of curves as well as the decreasing slope.

RELATED WORK
In [10], Hansen and Golbeck make a case for recommending playlists and other collections of items. The AutoDJ system of Platt et al. [11] is one of the early works on playlist generation that uses acoustic features of songs rather than a graph based representation. Random walk methods were used in [8], in order to generate lists of videos in a co-view graph. We formalized and presented our view of generating lists using random walks in introduction for recommending lists as an ordered package of items to users.
The HPP in a special case was studied recently by [7] and they defined a notion of Stable Clusters for the specific application of finding persistent chatter in the blogosphere. Unlike our setting, the graph associated with their application is -partite and acyclic. Absence of cycles makes their technical problem more tractable than ours. The most efficient algorithm presented in their work is a BFS based method that follows a dynamic programming approach.
We followed dynamic programming algorithm that also avoids cycles and found this approach extremely inefficient compared to RSA.
Rankjoin was first proposed by Ilyas et al. [26,25,24,30,33] to produce top-k join tuples in a relational database. We show how to convert Rankjoin to HPP. Furthermore, no one has studied Rankjoin with self-joins to the best of our knowledge. In [4], authors provide a comprehensive summary of this algorithm and do optimality analysis as done in the theoretical database literature. Their conclusion is that beyond = 2, we can not guarantee any optimality results for Rankjoin. This also matches our results regarding HPP being np-hard and inapproximable.

CONCLUSIONS AND FUTURE WORK
Finding the top-k heaviest paths in a graph is an interesting problem with many practical applications. We discuss the hardness of this problem. We focus on developing practical exact algorithms for this problem. We use an innovative top-k query processing algorithm. We motivate the problem from several different perspectives and discuss possible applications. We present a case study on core community detection. Our findings suggest that our case study can be further extended to a community detection tool that discovers the key influential people in a network represented by a weighted graph. Our future work will focus on more applications of RSA, specially those in network analysis, community detection, recommender systems and bioinformatics. We would also like to investigate more scalable algorithms and threshold update strategies within the same framework. We also intend to design probabilistic and robust heuris-tic algorithms that work under memory and other types of constraints such as edge distribution.