Hi Bhagya, Please provide the references for maximum clique and largest connected component (i.e. pegasus) algorithms.
Thanks Malith On Wed, Aug 10, 2016 at 9:04 PM, Bhagya Rupasinghe <[email protected]> wrote: > Hi all, > Implementation in Siddhi > > Maximum clique is used to identify the largest number of vertices in the > same entity which are connected to each other.In the Siddhi implementation, > input stream containing user IDs are added into a graph as vertices. And > then edge is created between them to show that they are linked.Finally > largest clique size is calculated and send as output stream. > > This implementation can be used to identify largest customer collection > when it comes to marketing by providing their relationships.We can use > social media data to find the relationships. > > Largest Connected component is the largest number of vertices which > connect to the vertex next to them.But they are not inter connected.This > is a big chain with respect to the largest clique.In siddhi we used user > IDs of users who are connected with each other as input data and calculated > largest connected component using pegasus algorithm.Finally largest > connected component will be send to the output stream. > On Aug 10, 2016 12:15 PM, "Malith Jayasinghe" <[email protected]> wrote: > >> Hi All, >> >> >> We are implementing 2 Siddhi Extensions 1) Largest Connected Component >> and 2) Maximum Clique. >> >> Using these extensions we can identify/detect the largest connected >> component and the maximum clique in a (large) undirected graph. A >> connected component/clique could represent a community that are >> currently involved in a particular topic etc. In the initial >> implementation we are considering only the undirected graphs in which >> edges have no orientation (direction). >> >> >> 1) Connected component: a connected component of an undirected graph is >> a subgraph in which any two vertices are connected to each other by >> paths. The following figure shows a graph with 3 connected components >> >> >> 2) Clique: The clique is an important concept in graph theory (also >> called a complete graph). It is defined as a graph where every vertex is >> connected to every other. This means that every vertex is reachable >> <https://en.wikipedia.org/wiki/Reachability> from every other vertex. In >> the graph below the maximal clique is 6-clique containing the vertices {A, >> G, H, J, K, M}. >> >> >> [1] https://en.wikipedia.org/wiki/Clique_(graph_theory) >> [2] https://en.wikipedia.org/wiki/Connected_component_(graph_theory) >> >> -- >> Malith Jayasinghe >> >> >> WSO2, Inc. (http://wso2.com) >> Email : [email protected] >> Mobile : 0770704040 >> Lean . Enterprise . Middleware >> >> _______________________________________________ >> Architecture mailing list >> [email protected] >> https://mail.wso2.org/cgi-bin/mailman/listinfo/architecture >> >> > _______________________________________________ > Architecture mailing list > [email protected] > https://mail.wso2.org/cgi-bin/mailman/listinfo/architecture > > -- Malith Jayasinghe WSO2, Inc. (http://wso2.com) Email : [email protected] Mobile : 0770704040 Lean . Enterprise . Middleware
_______________________________________________ Architecture mailing list [email protected] https://mail.wso2.org/cgi-bin/mailman/listinfo/architecture
