Information Technology Reference
In-Depth Information
underlying linkage patterns or building blocks[2] to have a better understanding
of the network's structural and functional properties.
Among the basic building blocks, maximal clique is a well-known sub-structure
and has applications in many different domains. In graph theory, an algorithm
for listing all maximal cliques in a graph can be used as a subroutine for solving
many NP -complete graph problems. If a given subgraph is the maximal clique
in some graph G , it is also the maximal independent set[3] in the complement
graph of G . Apparently, the solutions to the maximum independent set problem,
the maximum clique problem, and the minimum independent dominating prob-
lem must all be maximal cliques, and can be found by an algorithm that lists all
maximal cliques and retains the ones with the largest or smallest size. Lawler
(1976) observed that listing maximal independent sets can also be used to find
3-colorings of graphs: a graph can be 3-colored if and only if the complement of
one of its maximal independent sets is bipartite. In social network analysis[4],
a maximal clique represents a group of closely interrelated people, which is also
called the community structure. For social network researchers, individuals be-
longing to the same community are probable to have properties in common.
The communities in the blogs often correspond to topics of interest. Monitor-
ing the aggregate trends and opinions revealed by these communities provides
valuable insight to a number of business strategies and decisions. In bioinfor-
matics, maximal cliques are used to search for the common sub-topologies in a
set of protein structures[5]. Other more complex problems can also be modeled
as finding a clique or independent set of a specific type. All these applications
motivate many algorithms to enumerate all maximal cliques or equivalently, all
maximal independent sets eciently.
However, it is easy to see that enumerating all maximal cliques is also a NP -
problem[6], where a graph with n vertices can have as many as 3 n/ 3 maximal
cliques, of which some are of the maximum size. Meanwhile, many real world
networks often consist of millions of nodes and edges making the problem even
more challenging. Given graph G with n vertices and m edges, in the worst case,
Peamc runs with O ( Δ×M C ×Tri 2
P )timedelayandin O ( m + n )using P processing
elements, where Δ is the maximum degree of G , M C represents the size of the
maximum clique and Tri denotes the number of all triangles in G respectively.
12.3
Related Work
Traditionally, the study of networks has been the territory of graph theory.
While graph theory initially focused on regular graphs, since the 1950s large-
scale networks with no apparent design principles have been described as random
graphs, which were first studied by the famous mathematicians Paul Erdos and
Alfred Renyi [1].Accordingtothe Erdos - Renyi model, we start with n nodes
and connect every pair of nodes with probability p . The obtained graph has
expected pn ( n− 1 2 edges distributed randomly. This model has guided our think-
ing about real world networks for many decades since its introduction. Based
on this model, the maximal clique problem, being as one of the well-known
 
Search WWH ::




Custom Search