In social networks,
k-core is commonly used to measure the stability of a network. When a user in a
k-core leaves the network, other users may follow the user to leave. Hence, maintaining a key user is important to keep the
[...] Read more.
In social networks,
k-core is commonly used to measure the stability of a network. When a user in a
k-core leaves the network, other users may follow the user to leave. Hence, maintaining a key user is important to keep the stability of a network. It is known that an edge between two users models the relationship between the two users. In some scenarios, maintaining a relationship comes at a cost. Therefore, selectively in maintaining the relationships between users is crucial. In this paper, we for the first time conceive the concept of an edge-based minimal
k-core model. An edge-based minimal
k-core is a
k-core with a minimal number of edges. In other words, removing any edge in an edge-based minimal
k-core would make it not be a
k-core any more. Based on this model, we proposed two problems, namely, an edge-based minimal
k-core subgraph search (EMK-SS) and an edge-based minimal
k-core subgraph search with a query node
q (EMK-
q-SS). Given a graph
G, an integer
k, and a query node (a key user)
q, the EMK-
q-SS problem is to find all the edge-based minimal
k-cores containing the query node
q, and the EMK-SS problem is to find all the edge-based minimal
k-cores. We also theoretically prove that the two problems are both NP-complete. To deal with the proposed problems, we design two novel algorithms, namely the edge deletion algorithm and edge extension algorithm. Further, a graph partitioning technique is employed to speed up the computation. Comprehensive experiments on synthetic and real networks are conducted to demonstrate the effect and efficiency of our proposed methods.
Full article