A k-defective clique of an undirected graph G is a subset of its vertices that induces a nearly complete graph with a maximum of k missing edges. The maximum k-defective clique problem, which asks for the largest k-defective clique from the given graph, is important in many applications, such as social and biological network analysis. In the paper, we propose a new branching algorithm that takes advantage of the structural properties of the k-defective clique and uses the efficient maximum clique algorithm as a subroutine. As a result, the algorithm has a better asymptotic running time than the existing ones. We also investigate upper-bounding techniques and propose a new upper bound utilizing the conflict relationship between vertex pairs. Because the conflict relationship is common in many graph problems, we believe that this technique can be potentially generalized. Finally, experiments show that our algorithm outperforms state-of-the-art solvers on a wide range of open benchmarks. Our source code, as well as the experiment data, is open source and available https://github.com/cy-Luo000/Maximum-k-Defective-Clique.git.

Given a graph, the k-plex is a vertex set in which each vertex is not adjacent to at most k-1 other vertices in the set. The maximum k-plex problem, which asks for the largest k-plex from a given graph, is an important but computationally challenging problem in applications like graph search and community detection. So far, there is a number of empirical algorithms without sufficient theoretical explanations on the efficiency. We try to bridge this gap by defining a novel parameter of the input instance, g_k(G), the gap between the degeneracy bound and the size of maximum k-plex in the given graph, and presenting an exact algorithm parameterized by g_k(G). In other words, we design an algorithm with running time polynomial in the size of input graph and exponential in g_k(G) where k is a constant. Usually, g_k(G) is small and bounded by O(log(|V|)) in real-world graphs, indicating that the algorithm runs in polynomial time. We also carry out massive experiments and show that the algorithm is competitive with the state-of-the-art solvers. Additionally, for large k values such as 15 and 20, our algorithm has superior performance over existing algorithms.

P2P lending, as a novel economic lending model, has imposed new challenges about how to make effective investment decisions. Indeed, a key challenge along this line is how to align the right information with the right people. For a long time, people have made tremendous efforts in establishing credit records for the borrowers. However, information from investors is still under-explored for improving investment decisions in P2P lending. To that end, we propose a data driven investment decision-making framework, which exploits the investor composition of each investment for enhancing decisions making in P2P lending. Specifically, we first build investor profiles based on quantitative analysis of past performances, risk preferences, and investment experiences of investors. Then, based on investor profiles, we develop an investor composition analysis model, which can be used to select valuable investments and improve the investment decisions. To validate the proposed model, we perform extensive experiments on the real-world data from the world's largest P2P lending marketplace. Experimental results reveal that investor composition can help us evaluate the profit potential of an investment and the decision model based on investor composition can help investors make better investment decisions.