advertisement

advertisement

Information about Socialmatchmaking

Published on May 31, 2008

Author: epokh

Source: slideshare.net

The problem of matchmaking in electronic social networks is formulated as an optimization problem.

In particular, a function measuring the matching degree of fields of interest of a search profile with

those of an advertising profile is proposed.

In particular, a function measuring the matching degree of fields of interest of a search profile with

those of an advertising profile is proposed.

advertisement

2 III. THE MATCHMAKING PROBLEM 1. Deﬁnitions In computer science, the term matching in general A proﬁle consists of its owner, being an actor of the refers to the process of evaluating the degree of similarity electronic social network, a list of attributes of a given or of agreement of two objects. Each object is character- set A together with their values, a list of attribute sten- ized by a set of properties or attributes, which in many cils where each stencil represents a pair of an attribute systems are given by name-value pairs [3]. Matching name and its value range, and a list of ﬁelds of interest plays a vital role in many areas of computer science and specifying their respective levels of interest. Attributes communication systems. For instance, it is studied for re- are properties of the proﬁle owner such as age, height, source discovery and resource allocation in grid comput- weight, eye color, or hair color. and we therefore sub- ing where matchmaking services are needed to interme- sume them under the class “Owner” (Fig. 1). In princi- diate between resource requesters and resource providers [1]. Other examples are given by the problem of match- Interest ing demands and supply of business or personal proﬁles Owner 1 ∗ ﬁeld: String in online auctions, e-commerce, recruitment agencies, or id: String Proﬁle —— level: [−1, 1] 1 ∗ dating services. height: integer ——— 1 ∗ eye color: String —— Stencil ... attribute: String range: T A. Proﬁles FIG. 1: UML diagram of the data structure of a proﬁle and its relationship to the owner’s attributes, the attribute stencils and In most matching problems, the objects under consid- the ﬁelds of interest. An attribute stencil consists of an owner’s eration take asymmetric roles, viz., some try to search attribute name and its (searched or advertised) range. for information or request for a service, others try to ad- vertise information or provide a service. A single object ple, there are two diﬀerent types of attributes, subsumed may naturally do both activities at a time, in electronic in the two disjoint sets N and D such that the set A of social networks this even is the usual case. In the sequel attributes separates as we will therefore more accurately consider the matching of a search proﬁle, containing the requested information, A = N ∪ D. (1) and an advertising proﬁle presenting the provided infor- mation. The set N consists of the numerical attributes of the owner which take integer or real numbers as values, the Given a speciﬁc search proﬁle, the matchmaking prob- set D consists of discrete non-numerical values. (The lem then is to ﬁnd those advertising proﬁles which match diﬀerence between numerical and non-numerical is not it best, in a sense to be speciﬁed in the sequel. Gener- sharp, for instance a string could well be considered as alizations of this problem ask for best global matchings, numerical via a symbol code, as well as non-numerical given a whole set of search proﬁles and a set of adver- since it seldom makes sense to multiply or divide strings; tising proﬁles. For instance, the global pairwise match- in most cases, strings are better considered as non- making problem seeks pairs of search/advertising-proﬁles numerical.) such that the entity of the pairs matches the best under Correspondingly, the stencil of an attribute is deter- the constraint that any proﬁle is member of at most one mined by the attribute’s name and its range, being of a pair, the global multiple matchmaking problem searches certain set called Type T , for possibly multiple combinations of search and adver- tising proﬁles which as a whole match the best. The T = N ∪ D. (2) pairwise version of the problem typically occurs for dat- ing services or classical marriage matchmaking tasks, where N denotes the set of ranges for the numerical whereas the multiple version appears in grid computing attributes, or in brokering interest groups. In this paper we will focus on the local version of the N ⊂ {[a, b] : −∞ ≦ a, b ≦ ∞}, (3) matchmaking problem, i.e., ﬁnding an optimum advertis- i.e., N is a set of closed intervals [a, b] ⊂ R, and D ing proﬁle to a speciﬁed search proﬁle. Thus the match- denotes the set of ranges for the discrete non-numerical making problem is an optimization problem, and to for- attributes, mulate it precisely we have to specify the search space and the objective function. The search space will turn D ⊂ {E : E is a ﬁnite set or enum}, (4) out to be the set of pairs of the ﬁxed search proﬁle and the advertising proﬁles, and the objective function will i.e., D is a ﬁnite set or enum, speciﬁed by the respec- be a function measuring the “matching degree.” We will tive owner attributes determined by the system model. work out these notions in the next sections. We allow the empty set ∅ as null element in N and D.

3 If a given range R ∈ T contains only one element, say is the set of searched ﬁelds of interest with their desired R = {x}, then the stencil is often shortly written “p = x” levels, with the given mapping ls : Is → [−1, 1]). Note instead of “p ∈ R.” If, on the other hand, R = [x, ∞] that each of the pairs (p, Rs ), (p, Es ), (p, ls ) can be easily then we may write “p > x” instead of p ∈ R. For in- implemented as a table or a hash map. Analogously, an stance, “height = 180” means “height ∈ [180, 180],” or advertising proﬁle is given by “height ¿ 180” means “height ∈ [180, ∞].” On the other hand, a ﬁeld of interest is a name-value a = na ∪ da ∪ ia , (9) pair specifying the ﬁeld itself as well as its level ranging on a scale from −1 to 1, coded by the interpolation of where the three sets are deﬁned the same way as in the the following table, search case, with the index ‘s’ (for “search”) replaced by ‘a’ (for “advertising”). Level Meaning −1 aversion Example 1. In grid computing, a main matching prob- (5) lem is resource discovery and resource allocation [4, 8]. 0 indiﬀerence Assume a toy grid consisting of two resource providers 1 enthusiasm Haegar and Bond, and two resource requests by some The set of ﬁelds of interests is denoted by I and is a computational process. In our terminology, Bond and subset of words of a speciﬁed alphabet Σ, Haegar each oﬀer an advertising proﬁle, whereas the requests are represented by search proﬁles. Moreover, I ⊆ Σ∗ (6) in the widely used matchmaking framework Condor-G Usually, Σ is the set of ASCII or Unicode symbols. The [5, 7, 9, 10, 11], the proﬁles are called ClassAds (classiﬁed set I determines the set of all ﬁelds of interests available advertisements). Let us assume the proﬁles according to to the system. Depending on the system design, it may the following tables. be a ﬁxed set of words, or an arbitrary word over the alphabet Σ. Search Proﬁles owner = 194.94.2.21 owner = 194.1.1.3 B. The search space CPU ≥ 1.6 GHz memory ≥ 2 GB memory ≥ 1 GB Given a set S of search proﬁles s and a set A of adver- tising proﬁles a as input, the search space S of a global Advertising Proﬁles matchmaking problem is given by all pairs of search and owner = bond.cs.ucf.edu owner = 194.94.2.20 advertising proﬁles, i.e., S g = S × A. In this paper, how- CPU ≤ 3.6 GHz CPU = 2.5 GHz ever, we are considering the local matchmaking problem, memory ≤ 4.0 GB memory = 1.0 GB given a single search proﬁle s, i.e., S = {s}, and the search space In each column of a proﬁle there is listed its owner and S = {s} × A(s). (7) some attributes and their values. where A(s) = {a ∈ A : owner(a) = owner(s)}. A search Example 2. Assume a small social network for pooling proﬁle s itself is a set of the given attribute stencils ns , interest groups, consisting of three persons, Alice, Bob, ds , and of ﬁelds of interest is , and Carl, who provide search and advertising proﬁles ac- cording to the following tables. s = ns ∪ ds ∪ is , (8) where Search Proﬁles ns = {(p, Rs (p)) : p ∈ Ns } owner = Alice owner = Carl is the set of attribute-range pairs, with the given map- age ∈ [20,40] age ∈ [20,30] ping Rs : Ns → N from the set Ns of the searched nu- height > 180 merical attributes to their associated desired ranges (Rs tennis = 1.0 basketball = 1.0 associates to each numerical attribute p in Ns an interval chess = 0.5 Rs (p) = [a, b]), Advertising Proﬁles ds = {(p, Es (p)) : p ∈ Ds } owner = Alice owner = Bob owner = Carl is the set of attribute-set pairs, with the mapping Es : age = 25 age = 26 age = 31 Ds → D from the given set Ds of searched discrete at- height = 165 height = 182 height = 195 tributes to their desired sets or enums, (Es associates tennis = 1.0 tennis = 0.5 basketball = 1.0 discrete nonnumerical attribute p a set Es (p)), and chess = 0.5 basketball = −1.0 is = {(p, ls (p)) : p ∈ Is } basketball = 0.5

4 In each column of a proﬁle there is listed its owner, some with f = 0 meaning “total mismatch” and f = 1 mean- attributes and their values, and the ﬁelds of interests ing “perfect match.” In general, the matching degree will with their levels. For instance, Alice looks for someone be the weighted sum of several partial matching degrees, between 20 and 40 years of age being enthusiastic in ten- one for each property separately. Moreover, the match- nis and having some penchant to chess, whereas Carl ing degree of an attribute is calculated in a diﬀerent way seeks a tall person in the 20’s with highest preference for than the matching degree of a ﬁeld of interest. Proposals basketball. Looking at the advertising proﬁles in this so- for these diﬀerent kinds of matchings are introduced in cial network, one sees that Alice may contact Bob, but the following paragraphs. Carl cannot ﬁnd an ideal partner in this community. On the other hand, Alice would be a “better” partner for Carl than Bob, since she is partly interested in basket- 1. Matching degree of an attribute range ball. Formally Alice’s search proﬁle, for instance, is given as follows. The sets for the searched attributes and ﬁelds A function measuring the matching degree of ranges of interest are of an attribute has to quantify how a given advertised attribute stencil [aa , ba ] ﬁts into the stencil pattern given Ns = {age}, Ds = ∅, Is = {tennis, chess}, (10) by the corresponding range in the search proﬁle. In case of a numerical attribute, the stencil is given by a closed the mapping Rs is given by interval [a, b] ∈ D in case of a discrete-value attribute it is a set or enum E. [20, 40] if p = “age,” Rs (p) = (11) a. Numerical attribute intervals matching. To de- ∅ otherwise. termine the matching degree of a searched value range and the mapping ls is given by the table [as , bs ] with a given advwertised value range x ∈ R, we deﬁne the fuzzy step function he (x) = he (x; a, b) with p tennis chess a ≦ b and 0 < e < 1, as (12) ls (p) 1.0 0.5 ae − 1−e if (1 − e)a < x ≦ a, x e 1 if a < x ≦ b, The mapping Es does not exist since Ds = ∅. To sum he (x; a, b) = (18) up, Alice’s search proﬁle is given by 1+e − be if b < x ≦ (1 + e)b, e x 0 otherwise. sAlice = {(age, [20, 40])} (Fig. 2). The parameter e is called the fuzzy level . It ∪ {(tennis, 1.), (chess, .5), (basketball, .5)}, (13) denotes the relative length of the fuzzy transition region. The smaller e, the narrower this region, and the more Note in particular that ns,Alice = ∅. On the other hand, accurate an advertised attribute value must ﬁt into the the advertising proﬁles read searched interval. In the limit e → 0, the function he is A(sAlice ) = {aBob , aCarl } (14) ae be 1 where aBob = {(age, [26, 26]), (height, [182, 182])} a b x ∪ {(tennis, .5), (basketball, −1.)}. (15) FIG. 2: The fuzzy step function he (x) of Eq. (18). aCarl = {(age, [31, 31], (height, [195, 195])} the step function, and for a → −∞ or b → ∞, it tends ∪ {(basketball, 1.)}. (16) to one of the Heaviside step functions Hb (−x) or Ha (x), respectively. With the deﬁnitions If, for instance, the searched attribute is “height > sB = (sAlice , aBob ), sC = (sAlice , aCarl ), (17) 180” and an advertised attribute is “height = 165” then for a fuzzy level of e = 10%, we have the search space S = {sAlice } × {aBob , aCarl } = {sB , sC } 165 .9 consists of two feasible solutions. h0.1 (165; 180, ∞) = − = 0.16, (19) 18 .1 i.e., the matching degree is 16.7%. Then the matching degree of two numerical ranges [as , bs ] as search range C. A matching degree function and [aa , ba ] as advertised range are given by The matching degree of a search proﬁle and an adver- mn ([as , bs ], [aa , ba ]; e) = tising proﬁle is a real number f , typically 0 ≦ f ≦ 1, max [he (ba ; as , bs ), he (bs ; aa , ba )] . (20)

5 b. Features matching ﬁnite sets or enums. If the val- ues of speciﬁc attribute are constrained to be of a ﬁnite mi set, or an enum, say E then the matching degree is deter- 1 mined by the Boolean characteristic function χE deﬁned 0.75 0.5 1 0.25 0.5 by 0 -1 0 -0.5 la 0 -0.5 1 if x ∈ E, 0.5 χE (x) = (21) ls 1 -1 0 otherwise. FIG. 3: The matching degree function m = m(ls , la ) in Eq. (24). If the searched attribute, for instance, is “name ∈ {‘Smith’, ‘Taylor’}” and the advertised attribute is “name = ‘Tailor’” then E = {‘Smith’, ‘Taylor’} and 3. The total matching degree function χE (‘Tailor’) = 0, i.e., the matching degree is zero. Since the owner of an advertising proﬁle can advertise at most Putting together all partial matching degrees consid- one value for an attribute, we have ered above, we have to construct a function f : S → [0, 1] md (E, {x}) = χE (x). (22) as a weighted sum of them. We notice that any s ∈ S rep- resents a feasible solution of the matchmaking problem and has the form s = (s, a) where s is the given search 2. Matching degree of a ﬁeld of interest proﬁle (8) and a is one of the given advertising proﬁles (9) in the network. Then f deﬁned for each s ∈ S by First we notice that the matching degree as a function mn (Rs (p), Ra (p)) of the levels of interest ls for the search proﬁle and la for f (s) = the advertising proﬁle must be asymmetric. For instance, |Ns | + |Ds | + |Is | p∈Ns if ls = 0 and la = 1, i.e., the search is indiﬀerent with md (E(p), Ta (p)) respect to the ﬁeld of interest, and the advertising proﬁle + |Ns | + |Ds | + |Is | has la = 1, then the matching degree should be greater p∈Ds than 0, but if the search requires ls = 1 and la = 0 then mi (ls (p), la (p)) the matching degree should be zero. In the ﬁrst case, the + (27) |Ns | + |Ds | + |Is | searcher is indiﬀerent about the ﬁeld of interest, in the p∈Is second case he demands high interest. where Ra (p) and E(p) denote the attribute ranges of the Deﬁnition 3. An interest matching degree function is attribute p, la (p) is the advertised interest level of the a function m : [−1, 1]2 → [0, 1] such that the following ﬁeld of interest p, and the vertical bars | · | embracing a conditions are satisﬁed. set denote the number of its elements. Thus for the computation of the matching degree, the (ls , la ) (x, x) (0, ±1) (±1, 0) attributes and ﬁelds of interest of the search search pro- 1 (∀x ∈ [−1, 1]) (23) m(ls , la ) 1 2 0 ﬁle s are leading, i.e., it is s which determines what is tried to be matched. The, if an attribute p of the search The ﬁrst condition expresses the perfect matching of the proﬁle does not occur in the advertising proﬁle, then the diagonal, the second the search indiﬀerence, and the last matching degree functions mn (p) and md (p) vanish by the search necessity. deﬁnition. If, however, a searched ﬁeld of interest p ∈ is A possible matching degree function is given by does not occur in the advertised proﬁle, then it is the level la (p) which vanishes by deﬁnition. Note the crucial dif- mi (ls , la ) = max[ϕ(ls , la ), 0] (24) ference between null values of attributes and null values where of ﬁelds of interest in the advertising proﬁle: searched at- tributes are mandatory, and at least with respect to this (c2 − 1)(x − y)2 attribute there is a complete mismatch; if a ﬁeld of in- ϕ(x, y) = 1 − (25) c2 − 2 + (x − cy)2 terest, however, does not occur in the advertised proﬁle, it is indiﬀerent to its owner, but depending on the level with √ of interest in the search proﬁle, the matching degree may 1+ 7 be positive nonetheless. c= ≈ 1.823. (26) 2 Example 2 (revisited). For Alice’s search space we By construction, m(ls , la ) satisﬁes the conditions in (23) have the two solutions (17), i.e., and therefore is an interest matching degree function. It is asymmetric with respect to its arguments, since we mn ([20, 40], [26, 26]) mi (1, .5) + mi (.5, 0) 2 2 have m(ls , la ) = m(la , ls ) if and only if ls = la . On f (sB ) = + 3 3 the other hand, it is an even function, i.e., m(ls , la ) = 1 .5636 + .6308 m(−ls , −la ). = + = 0.7315 (28) 3 3

6 and of all weights wn : N → R+ , wd : N → R+ , wi : N → R+ . mn ([20, 40], [31, 31]) mi (1., 0) + mi (.5, 0) f (sC ) = + 3 3 IV. DISCUSSION 1 0 + .6308 = + = 0.5436 (29) 3 3 In this paper, a mathematical model of the match- Hence Bob’s advertising proﬁle has a matching degree making of search and advertising proﬁles in an electronic of 73.15% with Alice’s search proﬁle, whereas Carl’s social network is proposed. Basing on the data structure matches it only by 54.36%. described by Figure 1 and distinguishing between match- making of attribute ranges via stencils and matchmaking Notice that the objective function (27) is constructed of ﬁelds of interests via comparison, the matchmaking in such a way that each searched item p of a search proﬁle problem is formulated as an optimization problem, with has equal weight. If, however, each item should have the search space consisting of a ﬁxed search proﬁle and its own weight w(p), then the objective function (30) is several advertising proﬁles as in Eq. (7) and the match- easily be modiﬁed to ing degree as its objective function in Eq. (27). The main diﬃculty is to deﬁne a function measuring adequately the wn (p) matching degree of two ﬁelds of interest and obeying the f (s) = mn (Rs (p), Ra (p)) necessary conditions listed in Deﬁnition 3. A proposed wtot p∈Ns solution is the function given in Eq. (24) and depicted in wd (p) Figure 3. The implementation of a matchmaking service + md (E(p), Ta (p)) wtot in an electronic social network basing on this matching p∈Ds optimization is straightforward. wn (p) + mi (ls (p), la (p)) (30) wtot p∈Is Acknowledgments where wtot is the total sum I am indebted to Thomas Kowalski, Valerie Rinke, and wtot = wn (p) + wd (p) + wi (p) (31) Volker Weiß for valuable discussions. p∈Ns p∈Ds p∈Is [1] X. Bai, H. Yu, , Y. Ji, and D. C. Mari- [7] O. Lodygensky, G. Fedak, F. Cappello, V. N´ri, M. Livny, e nescu. ‘Resource matching and a matchmaking ser- and D. Thain. Xtremweb & condor sharing resources vice for an intelligent grid’. International Jour- between internet connected condor pools. In CCGRID, nal of Computational Intelligence, 1(3):197–205, 2004. pages 382–389. IEEE Computer Society, 2003. http://www.cs.ucf.edu/ xbai/ICCI04.pdf . [8] R. Prodan and T. Fahringer. Grid Computing: Ex- [2] J. A. Barnes. ‘Class and Committees in a Norwegian periment Management, Tool Integration, and Scientiﬁc Island Parish’. Human Relations, 7(1), 1954. Workﬂows. Springer-Verlag, Heidelberg Berlin, 1st edi- [3] A. de Vries. ‘XML framework for concept de- tion, 2006. scription and knowledge representation’, 2004. [9] R. Raman, M. Livny, and M. H. Solomon. Match- http://arxiv.org/cs.AI/0404030. making: Distributed resource management for high [4] I. Foster and C. Kesselman, editors. The Grid 2. throughput computing. In HPDC, pages 140–, 1998. Blueprint for a New Computing Infrastructure, Amster- http://dx.doi.org/10.1109/HPDC.1998.709966 . dam, 2004. Elsevier. [10] D. Thain and M. Livny. Building reliable clients and [5] F. J. Gonz´lez-Casta˜o, J. Vales-Alonso, M. Livny, a n services. In Foster and Kesselman [4], pages 285–318. E. Costa-Montenegro, and L. E. Anido-Rif´n. Condor o [11] D. Thain, T. Tannenbaum, and M. Livny. Distributed grid computing from mobile handheld devices. Mobile computing in practice: the condor experience. Concur- Computing and Communications Review, 7(1):117–126, rency - Practice and Experience, 17(2-4):323–356, 2005. 2003. http://doi.acm.org/10.1145/881978.882005 . [12] S. Wasserman and K. Faust. Social Network Analysis. [6] R. A. Hill and R. I. M. Dunbar. ‘Social net- Cambridge University Press, Cambridge, 1994. work size in humans’. Human Nature, 14(1), 2002. http://www.liv.ac.uk/evolpsyc/Hill Dunbar networks.pdf .

We're about Social Matchmaking and we're currently in BETA due to launch soon.

Read more

· SocialMatchMaking.Com · Whatt · Moon Bend Net Services----- to come. Eddie S. Reckers PH# 415.948.1551 454 Ivy Street San Francisco, CA 94102 ...

Read more

socialmatchmaking.com.au bitesizedental.com gringotacoshop.com visionairetechnology.com innerjoyhomecare.com fresnolatinofilmfestival.com socialsaving.com

Read more

Ik organiseer mooie programma's en projecten, verbindt mensen en ideeën, Impact staat hierbij voorop

Read more

Welcome to Moonbend.com. This is your first post. Edit or delete it, then start blogging! Read more

Read more

A system and a method for providing the feedback about a game player and improving social match making (SOCIALMATCHMAKING) 199 : 253 ...

Read more

1. 1 2. 2Copyright © 2009The Wallace FoundationAll rights reserved.This publication was produced as part of a commitment by The Wallace Foundation to ...

Read more

th.wsgiga.com

Read more

## Add a comment