The SGM technology offers a solution for the matching of profiles and their environments in graph type data structures. It solves some of the problems of current sub-graph matchers such as the data processing cost and adaptability to new data characteristics and graph problems. Sub- graph matching is a technique which is employed in many fields, and is of special interest to online applications with user profile and activity data, such as social networks, applications which match user profiles (employment webs, partner search, etc.).
BACKGROUND
In Online Social Networks (OSNs) and User Applications, it is often of interest to find users with a similar characteristics to a given profile. For example, a user with a similar number of friends who have similar likes, dislikes, interrelations, skills or historical activity, However, the computational cost and complexity of this type of search, called a ‘graph search’ is often prohibitive. Exact (isomorphic) and approximate methods can be applied to perform matching. Approximate methods give an acceptable result for applications such as OSNs. Applications include user experience enhancement by offering new search tools, publicity targeting and recommender systems for pairing candidates with profiling requirements.
THE TECHNOLOGY
SGM uses pre-calculated statistics describing a given sub-graph and all other sub- graphs in a complete graph in order to find the closest matches. SGM can be calibrated on specific datasets in order to capture their idiosyncrasies. The descriptive statistics can also be adapted to incorporate new data attributes. Once calibrated, the runtime version finds the top N similar sub-graphs incurring a low computation cost. It can be incorporated in an existing application as a library of functions (API).
ADVANTAGES
Can be customized for search requirements and data characteristics
The matching offers a higher level of sophistication over simpler tabular searching methods
Can be embedded in almost any native application, SQL, etc.
Lower computational cost
STATE OF DEVELOPMENT
A prototype was first developed in Java and statistically tested on standard benchmark graph datasets. From the results, we demonstrated that the matching precision is close to the best exact matcher (VF2) and has a much lower computational cost. Recently, we have successfully performed a proof of concept for a large online employment website, which matches professionals to projects depending on their experience and know-know.
INTELLECTUAL PROPERTY
A patent covering the matching methodology and technique was filed in the European Patent Office in 2013, and was upgraded to a PCT Patent Application in 2014.
MARKET OPPORTUNITY
Sub-graph matching can be used for any online application in which social graphs and graphs of user activity can be exploited. Internet application providers will be especially interested in this technology.
COMMERCIAL OPPORTUNITY
Technology available for licensing and customization.
CONTACT
Marc Santandreu
Technology Transfer Unit
(+34) 93 542 28 96
[email protected]
KEYWORDS
Graph, matching, user profiles, online social networks.
Ref: TEC-0085/P-0026
Fact Sheet
