The link structure of the Web is generally viewed as the webgraph. Web structure mining is a research area that mainly aims to find hidden communities by focusing on the webgraph, and communities or their cores are supposed to constitute dense subgraphs. Therefore, structure mining can actually be realized by enumerating such substructures, and Kleinberg's biclique model is well-known among them. In this paper, we examine some candidate substructures, including conventional bicliques, and attempt to find useful information from the real web data. Especially, we newly exploit isolated cliques for our experiments of structure mining. As a result, we discovered that isolated cliques that lie over multiple domains can stand for useful communities, which implies the validity of isolated clique as a candidate substructure for structure mining. On the other hand, we also observed that most of isolated cliques on the Web correspond to menu structures and are inherent in single domains, and that isolated cliques can be quite useful for detecting harmful link farms.

The link structure of the Web is generally viewed as a webgraph. One of the main objectives of web structure mining is to find hidden communities on the Web based on the webgraph, and one of its approaches tries to enumerate substructures, each of which corresponds to a set of web pages of a community or its core. Research has shown that certain substructures can find sets of pages that are inherently irrelevant to communities. In this paper, we propose a model, which we call contracted webgraphs, where such substructures are contracted into single nodes to hide useless information. We then try structure mining iteratively on those contracted webgraphs since we can expect to find further hidden information once irrelevant information is eliminated. We also explore the structural properties of contracted webgraphs from the viewpoint of scale-freeness, and we observe that they exhibit novel and extreme self-similarities.

Optimizing the computing process of relational databeses is important in order to increase their applicability. The process consists of operations involving many relational tables. Among basic operations, joins are the most important because they require most of the computational time. In this paper, we consider to execute such joins on many relational tables by the merge-scan method, and try to find the optimum join order that minimizes the total size of intermediate tables (including the final answer table). The cost is important in its own right as it represents the memory space requirement of the entire computation. It can be also viewed as an approximate measure of computational time. However, it turns out that the problem is solvable in polynomial time only for very restricted special cases, and in NP-hard in general.

Consider a random digraph G=(V,A), where |V|=n and an arc (u,v) is present in A with probability p(n) independent of the existence of the other arcs. We discuss the expected number of vertices reachable from a vertex, the expected size of the transitive closure of G and their related topics based on the properties of reachability, where the reachability from a vertex s to t is defined as the probability that s is reachable to t. Let γn,p(n) denote the reachability s to t (s) in the above random digraph G. (In case of s=t, it requires another definition. ) We first present a method of computing the exact value of γn,p(n) for given n and p(n). Since the computation of γn,p(n) by this method requires O(n3) time, we then derive simple upper and lower bounds γn,p(n)U and γn,p(n)L on γn,p(n), respectively, and in addition, we give an upper bound n,p(n) on γn,p(n)U, which is easier to analyze but is still rather accurate. Then, we discuss the asymptotic behavior of n,p(n) and show that, if p(n)=α/(n-1), limnn,p(n) converges to one of the solutions of the equation 1-x-e-α x=0. Furthermore, as for (n) and (n), which are upper bounds on the expected number of reachable vertices and the expected size of the transitive closure of G, resp. , it turns out that limn(n) =α/(1-α) if p(n)=α/(n-1) for 0<α<1; otherwise either 0 or , and limn(n)=α if p(n)=α/(n-1)2 for α0; otherwise either 0 or .

Betweenness centrality is one of the most significant and commonly used centralities, where centrality is a notion of measuring the importance of nodes in networks. In 2001, Brandes proposed an algorithm for computing betweenness centrality efficiently, and it can compute those values for all nodes in O(nm) time for unweighted networks, where n and m denote the number of nodes and links in networks, respectively. However, even Brandes' algorithm is not fast enough for recent large-scale real-world networks, and therefore, much faster algorithms are expected. The objective of this research is to theoretically improve the efficiency of Brandes' algorithm by introducing graph decompositions, and to verify the practical effectiveness of our approaches by implementing them as computer programs and by applying them to various kinds of real-world networks. A series of computational experiments shows that our proposed algorithms run several times faster than the original Brandes' algorithm, which are guaranteed by theoretical analyses.

Shakashaka is a pencil-and-paper puzzle proposed by Guten and popularized by the Japanese publisher Nikoli (like Sudoku). We determine the computational complexity by proving that Shakashaka is NP-complete, and furthermore that counting the number of solutions is #P-complete. Next we formulate Shakashaka as an integer-programming (IP) problem, and show that an IP solver can solve every instance from Nikoli's website within a second.